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


2019-5-2 期四  

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

1c5c5349ddac3659bdeccb83c7f6c286.png

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

前序遍历,先访问根结点,然后在访问左子树,最后访问右子树。可以利用栈的特点,这里我结合了队列和栈的特点来实现。先压入树,取出根节点。先把根节点值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)

f7853f67cc53e4f8d6b880bfada77e04.png

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



Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Leetcode PHP题解--D50 933. Number of Recent Calls

>> 下一篇: Leetcode基础刷题之PHP解析( 98. Validate Binary Search Tree)