题目
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
示例:
二叉树:[3,9,20,null,null,15,7],
返回其层次遍历结果:
1 2 3 4 5
| [ [3], [9,20], [15,7] ]
|
思路
把所有不为空的节点加入到列表,循环将子节点放到列表,直到所有子节点为空
关键点
复杂度
代码
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
|
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 }
|