Leetcode树的层次遍历之PHP解析(102. Binary Tree Level Order Traversal)
2019-5-30 星期四 开始吧
这周想把之前的关于树的题目总结一下 。
上一题链接Leetcode基础刷题之PHP解析(119. Pascal's Triangle II)
题目描述
给定一棵树,按照他的层次进行遍历,返回。
题目分析
DFS和BFS都可以解,竟然已经要我们按照层打印了,那么先使用BFS,思路就是先判断树是否是空,不是空加入一个队列的结构中,如果队列不为空,取出头元素,那么当前元素表示的就是当前这一层了,所以只需要遍历这一层里的所有的元素即可,然后下一层....
xxxxxxxxxx
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的话,就是一条路走到黑,然后再重新一路路的退回来再找下一路,所以这样的话,每一次我们需要记录一下当前他所在的这个点属于哪一层即可,代码用递归实现。
xxxxxxxxxx
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
No Comments