[leetcode]二叉树的广度优先搜索-层序遍历
题目描述
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
示例:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
算法实现
递归版(php)
结果的一维元素数量应等于树的深度，所以当深度$depth>=$count的时候要为该层节点结果扩充新的空间，先遍历左子树，在遍历右子树。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31/**
* 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 {
public $result = [];
public $stack = [];
/**
* @param TreeNode $root
* @return Integer[][]
*/
function levelOrder($root) {
$this->doTraverse($root,0,$this->result);
return $this->result;
}
function doTraverse($node,$depth,&$result){
if($node==null){
return;
}
if ($depth >= count($result))
array_push($result,[]);
array_push($result[$depth],$node->val);
$this->doTraverse($node->left, $depth + 1, $this->result);
$this->doTraverse($node->right, $depth + 1, $this->result);
}
}
迭代版(php)
从根节点开始入栈，首先统计当前栈元素数量，循环这部分元素进行出栈保存结果及子节点入栈操作，当栈不为空则继续前两步1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
* 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 {
public $result = [];
public $stack = [];
/**
* @param TreeNode $root
* @return Integer[][]
*/
function levelOrder($root) {
if($root==null){
return [];
}
$node = $root;
$this->stack[] = $node;
do{
$count = count($this->stack);
$item_result = [];
while($count>0){
$node = array_shift($this->stack);
$item_result[] = $node->val;
if($node->left!=null){
$this->stack[] = $node->left;
};
if($node->right!=null){
$this->stack[] = $node->right;
}
$count--;
}
$this->result[] = $item_result;
}while(!empty($this->stack));
return $this->result;
}
}