LeetCode 102 二叉树的层序遍历

给你二叉树的根节点 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

解题：

func levelOrder(root *TreeNode) [][]int {
	var r [][]int
	stack := []*TreeNode{root}
	for len(stack) > 0 {
		var tmp []int
		var tmpStack []*TreeNode
		for _, v := range stack {
			if v != nil {
				tmp = append(tmp, v.Val)
				tmpStack = append(tmpStack, v.Left, v.Right)
			}
		}
		if len(tmpStack) > 0 {
			r = append(r, tmp)
			stack = tmpStack
		} else {
			stack = []*TreeNode{}
		}
	}
	return r
}

官方解答：

1.广度优先搜索

func levelOrder(root *TreeNode) [][]int {
	var ret [][]int
	if root == nil {
		return ret
	}
	q := []*TreeNode{root}
	for i := 0; len(q) > 0; i++ {
		ret = append(ret, []int{})
		var p []*TreeNode
		for j := 0; j < len(q); j++ {
			node := q[j]
			ret[i] = append(ret[i], node.Val)
			if node.Left != nil {
				p = append(p, node.Left)
			}
			if node.Right != nil {
				p = append(p, node.Right)
			}
		}
		q = p
	}
	return ret
}