Leetcode树的层次遍历之PHP解析(102. Binary Tree Level Order Traversal)

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

内容简介:这周想把之前的关于树的题目总结一下 。

2 0 1 9 -5 -30   期四  

这周想把之前的关于树的题目总结一下 。

Leetcode基础刷题之 PHP 解析(119. Pascal's Triangle II)

Leetcode树的层次遍历之PHP解析(102. Binary Tree Level Order Traversal)

给定一棵树,按照他的层次进行遍历,返回。

DFS和BFS都可以解,竟然已经要我们按照层打印了,那么先使用BFS,思路就是先判断树是否是空,不是空加入一个队列的结构中,如果队列不为空,取出头元素,那么当前元素表示的就是当前这一层了,所以只需要遍历这一层里的所有的元素即可,然后下一层....

class Solution {

    /**
     * @param TreeNode $root
     * @return Integer[][]
     */
    function levelOrder($root) {
        if(empty($root)) return [];
        $result=[];
        $queue=[];
        array_push($queue,$root);
        while(!empty($queue)){
            $count=count($queue);
            $leveQueue=[];
            for($i=0;$i<$count;$i++){
                $node=array_shift($queue);
                array_push($leveQueue,$node->val);
                if($node->left) array_push($queue,$node->left);
                if($node->right) array_push($queue,$node->right);
            }
            array_push($result,$leveQueue);
        }
        return $result;
    }
}

如果使用DFS的话,就是一条路走到黑,然后再重新一路路的退回来再找下一路,所以这样的话,每一次我们需要记录一下当前他所在的这个点属于哪一层即可,代码用递归实现。

class Solution {

    /**
     * @param TreeNode $root
     * @return Integer[][]
     */
    function levelOrder($root) {
        if(empty($root)) return [];
        $result=[];
        $this->helper($result,$root,0);
        return $result;
    }
    function helper(&$result,$node,$level){
        if(empty($node)) return ;
        if(count($result)<$level+1){
            array_push($result,[]);
        }
        array_push($result[$level],$node->val);
        $this->helper($result,$node->left,$level+1);
        $this->helper($result,$node->right,$level+1);

    }
}

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


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

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

再启动

再启动

[日] 大前研一 / 田龙姬、金枫 / 中华工商联合出版社有限责任公司 / 2010-1 / 29.00元

1、“全球管理大师”、“日本战略之父”大前研一,职场励志最新巨作。 2、2010年1月中华工商联合出版社有限责任公司与日知公司继《货币战争2》《中国大趋势》之后,再度联手,重磅推出。 3、震撼中国职场的宗师级巨作,势必引领2010年中国职场4、世界著名出版商小学馆授予独家中文简体出版权。 5、试问,哪个老板不希望自己的员工不断实现自身的“再启动”呢? 6、只有不断激励鞭策自......一起来看看 《再启动》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

MD5 加密
MD5 加密

MD5 加密工具

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

在线 XML 格式化压缩工具