内容简介:这周想把之前的关于树的题目总结一下 。
2 0 1 9 -5 -30 星 期四 开 始 吧
这周想把之前的关于树的题目总结一下 。
上 一 题 链 接 Leetcode基础刷题之 PHP 解析(119. Pascal's Triangle II)
题 目 描 述
给定一棵树,按照他的层次进行遍历,返回。
题 目 分 析
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
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 数组常见的遍历循环方法、数组的循环遍历的效率对比
- C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比(Windows VirtualStudio)——遍历和删除
- Js遍历数组总结
- 遍历
- 遍历 DOM 注意点
- MySQL 实现树形的遍历
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。