Leetcode基础刷题之(94. Binary Tree Inorder Traversal)

明天再更新一篇400以内树的题目，就差不多把400以内的树的题目刷完了。

上一题链接Leetcode基础刷题之PHP解析(98. Validate Binary Search Tree)

题目描述

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

题目分析

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

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

Github整理地址：https://github.com/wuqinqiang/leetcode-php