给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

题目

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

案例

例如:
给定二叉树: [3,9,20,null,null,15,7],

1
2
3
4
5
6
7
8
9
10
11
   3
/ \
9 20
/ \
15 7
返回其层次遍历结果:
[
[3],
[9,20],
[15,7]
]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

递归

因为是按照层进行遍历,且每一层的 数据 都要存放在数组中,因此需要设置一个二维数组存放;遍历的时候,从最顶层开始递归,每递归一层层数+1,然后只需要将每一层的一维数组进行追加相应的数据即可 ;

代码思路

首先定义一个二维数组 levels := [][]int{}
如果当前层数为0,需要进行levels = make(levels,[]int{val})
如果当层数中的数据不为0,则直接追加数据;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func levelOrder(root *TreeNode) [][]int {
//定义的二维数组
levels :=[][]int{}
if root == nil{
return levels
}

return helper(root,0,levels)
}
func helper(root *TreeNode,curlevel int,levels [][]int)([][]int){
//某一层递归结束的条件
if root == nil{
return levels
}
if len(levels) == curlevel{
levels = append(levels,[]int{root.Val})
}else{
levels[curlevel] = append(levels[curlevel],root.Val)
}
levels = helper(root.Left,curlevel+1,levels)
levels = helper(root.Right,curlevel+1,levels)
return levels
}

非递归

非递归需要按照层次遍历出每一个数据追加到数据结构中,因为每一层的数据追加完成之后,需要到下一层的数据,因此需要保证数据结构中的长度为每一层的长度,因此需要对先进行填充的数据丢弃,因此可以用队列,在Go中可以使用切片模拟队列;

代码思路

首先需要定义一个结果集的 二维数组;
定义一个存放结点的 切片来模拟队列;
循环判断 队列中的长度,当 队列中的长度为 0表示遍历完了数据;
定义一个临时数组存放每一层的数据;
循环整个队列,移除头部的数据到临时数组中,同时追加该结点的 左右子节点;

代码如下

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
func levelOrder(root *TreeNode) [][]int {
//最终结果
result :=[][]int{}
//用数组模拟队列存放
que :=[]*TreeNode{}
if root == nil{
return result
}
que = append(que,root)
for len(que)>0{
//定义一个指向当前节点的指针数组,存放每一层的数组
current :=[]int{}
//重要,表示当前需要遍历的队列的长度
l :=len(que)
for i:=0;i<l ;i++{
//头节点
node :=que[0]
current = append(current,node.Val)
//维护队列
que = que[1:]
if node.Left !=nil{
que = append(que,node.Left)
}
if node.Right !=nil{
que = append(que,node.Right)
}
}
result = append(result,current)
}
return result
}