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

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


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

3554003996ca7d87fe1ee89f8229470b.png

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

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

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

吴亲库里 has written 85 articles

情绪只是对自己无能的愤怒

积分:4152 等级:P8 职业:php 城市:杭州

0 条回复

登录后才能进行评论,立即登录?