Skip to content

Latest commit

 

History

History
87 lines (73 loc) · 2.7 KB

94.md

File metadata and controls

87 lines (73 loc) · 2.7 KB

##Leetcode基础刷题之PHP解析(94. Binary Tree Inorder Traversal)
. 2019-05-06 吴亲库里 库里的深夜食堂

✏️题目描述

给定一个二叉树,返回其中序遍历:左->根->右,当然这道题要求的是用非递归来完成。前序后序在之前的一篇文章有非递归实现,特意留下中序,用递归和非递归一起实现。

✏️题目实例


✏️题目分析

对于树这种题目,我们一般都会利用栈和队列的特性来完成,递归的话定义一个辅助函数,我这里存储树的时候利用栈后进先出的特点,最后的值利用队列的特性。


   /**
   * Definition for a binary tree node.
   * class TreeNode {
   *     public $val = null;
   *     public $left = null;
   *     public $right = null;
   *     function __construct($value) { $this->val = $value; }
   * }
   */
  class Solution {
  
      /**
       * @param TreeNode $root
       * @return Integer[]
       */
      function inorderTraversal($root) {
         $res=[];
          $this->helper($root,$res);
          return $res;
      }
      
      function helper($root,&$res){
          if($root !=null){
              if($root->left !=null){
                  $this->helper($root->left,$res);
              }
              array_push($res,$root->val);
              if($root->right !=null){
                  $this->helper($root->right,$res);
              }
          }
      }
  }

✏️迭代

如果是迭代的话,套路还是一样的。先将根节点压入栈中,然后将其所有的左子节点依次压入栈中,取出栈顶元素,保存至队列中,再把指针指向他的右子节点上,如果存在右子节点,循环又把右子节点的左子节点压入栈中,保证了中序遍历的顺序。

  /**
   * @param TreeNode $root
   * @return Integer[]
   */
  function inorderTraversal($root) {
      $res=[];
      $data=[];
      while(!empty($res) || $root !=null){
          while($root !=null){
              array_unshift($res,$root);
              $root=$root->left;
          }
          $root=array_shift($res);
          array_push($data,$root->val);
          $root=$root->right;
      }
      return $data;
  }

联系