Leetcode基础刷题之PHP解析( 144. 145)

2019-5-2 星期四  开始吧

上一题链接Leetcode基础刷题之PHP解析(230. Kth Smallest Element in a BST)

题目描述

使用非递归来完成二叉树的前序遍历。

题目分析

前序遍历，先访问根结点，然后在访问左子树，最后访问右子树。可以利用栈的特点，这里我结合了队列和栈的特点来实现。先压入树，取出根节点。先把根节点值push到队列中，然后把右子树压入栈中，最后压入左子树。返回队列。当然你可以调整成你想要的实现方式。

/**
 * 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 preorderTraversal($root) {
        $res=[];
        $list=[];
        array_unshift($res,$root);
        while(!empty($res)){
           $current=array_shift($res);
           if($current==null) continue;
            array_push($list,$current->val);
            array_unshift($res,$current->right);
            array_unshift($res,$current->left);           
        }
        return $list;
        
    }
}

二叉树的后序遍历非递归(145)

    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    function postorderTraversal($root) {
         $tree=[];
         $res=[];
        array_unshift($tree,$root);
        while(!empty($tree)){
            $node=array_shift($tree);
            if($node==null) continue;
            array_unshift($res,$node->val);
            array_unshift($tree,$node->left);
            array_unshift($tree,$node->right);
        }
        return $res;
    }

其实都是一个套路，至于中序遍历，只要理解了规则，实现是一样的，当然了，你也可以试着用递归也实现。

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