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

栏目: PHP · 发布时间: 6年前

2 0 1 9 -5 -2   期四    

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

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

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

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

Leetcode基础刷题之PHP解析( 144. 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


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Coding the Matrix

Coding the Matrix

Philip N. Klein / Newtonian Press / 2013-7-26 / $35.00

An engaging introduction to vectors and matrices and the algorithms that operate on them, intended for the student who knows how to program. Mathematical concepts and computational problems are motiva......一起来看看 《Coding the Matrix》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试