94.md

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

:pencil2:题目描述

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

:pencil2:题目实例

​

---

:pencil2:题目分析

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

---

   /**
   * 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);
              }
          }
      }
  }

:pencil2:迭代

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

  /**
   * @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;
  }

---

联系

​