【Leetcode038】二叉树的层序遍历

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

借助队列，先将根节点入队，进入循环来遍历队列。队头出队，然后将左右子节点入队，直至没有左右子节点。最后将队列中剩下的全部取出，此时是最后一层的节点。

func levelOrder(root *TreeNode) [][]int {
    queue := make([]*TreeNode, 0)     // 队列
    res := make([][]int, 0)       // 结果
    if root == nil{
        return nil
    }
    queue = append(queue, root)
    for len(queue)>0{
        n := len(queue)     // 下面循环中queue是变化的，所以先保存到n
        var tmp []int       // 中间结果，临时存放每层节点
        for i:=0; i 0{
            res = append(res, tmp)
        }
    }
    return res
}

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

深度优先搜索按照中序遍历的顺序进行，定义一个二维数组，第一个索引对应节点所在层数，第二个索引对应节点在该层的位置。使用递归时，需要传入一个参数depth，代表访问节点所在的层数。

func levelOrder(root *TreeNode) [][]int {
    var res [][]int     // 结果
    var traversal func(node *TreeNode, depth int)
    traversal = func(node *TreeNode, depth int){
        if node == nil{     // 结束条件，到达叶子节点
            return
        }
        if len(res) == depth{   // 如果深度增加，就再申请res[]
            res = append(res, []int{})
        }
        res[depth] = append(res[depth], node.Val)   // 将节点加入对应行
        if node.Left != nil{    // 遍历左子树
            traversal(node.Left, depth+1)
        }
        if node.Right != nil{   // 遍历右子树
            traversal(node.Right, depth+1)
        }
    }
    traversal(root, 0)
    return res
}

• 时间复杂度：O(n)
• 空间复杂度：O(h)。h指树的高度。