102. 二叉树的层序遍历（中等）

• 难度: 中等
• 考察: 二叉树
• 来源: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

题目

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

示例：
二叉树：[3,9,20,null,null,15,7],

  3
 / \
9  20
  /  \
 15   7

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

思路

把所有不为空的节点加入到列表，循环将子节点放到列表，直到所有子节点为空

关键点

• 广度遍历

复杂度

• 时间复杂度：O(N)
• 空间复杂度：O(N)

代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}
	result := [][]int{{root.Val}}
	nodes := []*TreeNode{root}
	for len(nodes) > 0 {
		var childVals []int
		var tempNodes []*TreeNode
		for _, node := range nodes {
			if node.Left != nil {
				childVals = append(childVals, node.Left.Val)
				tempNodes = append(tempNodes, node.Left)
			}
			if node.Right != nil {
				childVals = append(childVals, node.Right.Val)
				tempNodes = append(tempNodes, node.Right)
			}
		}
		nodes = tempNodes
		if len(childVals) > 0 {
			result = append(result, childVals)
		}
	}
	return result
}