题目

提示

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

解题思路

解法一：递归

这个题目是二叉树的层序遍历，使用广度优先搜索（BFS）来实现。用递归的方式来实现搜索很快也很容易理解：

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func getNode(node *TreeNode, depth int, result *[][]int) {
	if node == nil {
		return
	}

	if len(*result) < depth+1 {
		*result = append(*result, make([]int, 0))
	}

	(*result)[depth] = append((*result)[depth], node.Val)

	if node.Left != nil {
		getNode(node.Left, depth+1, result)
	}

	if node.Right != nil {
		getNode(node.Right, depth+1, result)
	}
}

func levelOrder(root *TreeNode) [][]int {
	result := make([][]int, 0)
    getNode(root, 0, &result)
    return result
}

这里直接把每一层的深度和用来存储最终遍历结果的二维数组传入到递归函数中。每次递归的时候判断当前节点是否为空，如果不为空就把当前节点的值添加到对应深度的数组中，然后继续递归左子树和右子树。这样就可以实现二叉树的层序遍历了。
这个方法的时间复杂度是 O(n)，空间复杂度是 O(n)，其中 n 是二叉树的节点数。

解法二：非递归

当然所有递归都可以用非递归来实现，这里也是一样，可以申请一个数组用来存储当前层的节点，然后把当前层的节点全部遍历完之后再把下一层的节点添加到数组中。这样也可以实现二叉树的层序遍历了：

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
func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}

	result := make([][]int, 0)
	nodes := make([]*TreeNode, 1)
	levels := make([]int, 1)
	i := 0
	levels[0] = 0
	nodes[0] = root

	for {
		if i > len(nodes)-1 {
			break
		}

		node := nodes[i]
		level := levels[i]

		if level+1 > len(result) {
			result = append(result, make([]int, 0))
		}

		result[level] = append(result[level], node.Val)

		if node.Left != nil {
			nodes = append(nodes, node.Left)
			levels = append(levels, level+1)
		}

		if node.Right != nil {
			nodes = append(nodes, node.Right)
			levels = append(levels, level+1)
		}

		i++
	}
	return result
}

这里需要注意的就是要判断一下 root 是否为空，如果为空的话直接返回一个空的二维数组。然后用两个数组来存储当前层的节点和当前层的深度，最后遍历完所有的节点之后返回结果。这个方法的时间复杂度也是 O(n)，空间复杂度也是 O(n)，其中 n 是二叉树的节点数。这个方法的空间复杂度比递归的方法要高，因为需要额外申请两个数组来存储当前层的节点和深度，但是在实际使用中，估计这个方法的性能会更好一些，因为不需要频繁地进行函数调用和返回。