102. Binary Tree Level Order Traversal

102. 二叉树的层序遍历

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

示例 1：

img

输入：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

1. 广度优先 BFS

使用队列进行广度优先遍历.

1.1 双队列

使用两个队列, 分别代表当前层和下一层的节点.

1. 当前节点从q1出队
2. 将子节点加入q2
3. 若q1为空, 当前层结束, 交换q1, q2.

func levelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    
    if root == nil {
        return res
    }

    // Queue
    q1 := []*TreeNode{root}
    q2 := []*TreeNode{}
    
    vals := []int{}
    for len(q1) > 0 {
        cur := q1[0]
        q1 = q1[1:]
        vals = append(vals, cur.Val)

        if cur.Left != nil {
            q2 = append(q2, cur.Left)
        }
        if cur.Right != nil {
            q2 = append(q2, cur.Right)
        }

        if len(q1) == 0 {
            q1, q2 = q2, q1
            res = append(res, vals)
            vals = []int{}
        }
    }

    return res
}

1.2 单队列

使用变量记录当前层节点数即可.

func levelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    if root == nil {
        return res
    }

    // Queue
    q := []*TreeNode{root}
    curCnt := 1 // 当前层节点数
    nextCnt := 0 // 下一层节点数
    vals := []int{}
    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        vals = append(vals, cur.Val)
        curCnt--

        if cur.Left != nil {
            q = append(q, cur.Left)
            nextCnt++
        }
        if cur.Right != nil {
            q = append(q, cur.Right)
            nextCnt++
        }

        if curCnt == 0 {
            curCnt = nextCnt
            nextCnt = 0
            res = append(res, vals)
            vals = []int{}
        }
    }

    return res
}   

2. 深度优先 DFS

深度优先也可以解决.

2.1 递归

前序

func levelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    if root == nil {
        return res
    }

    dfsPreorder(root, 0, &res)
    return res
}

func dfsPreorder(root *TreeNode, depth int, res *[][]int) {
    if root == nil {
        return 
    }

    if len(*res) < depth+1 {
       *res = append(*res, []int{})
    }
    (*res)[depth] = append((*res)[depth], root.Val)
    
    dfsPreorder(root.Left, depth+1, res)
    dfsPreorder(root.Right, depth+1, res)
}

中序

func levelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    if root == nil {
        return res
    }
    dfsInorder(root, 0, &res)
    return res
}

func dfsInorder(root *TreeNode, depth int, res *[][]int) {
    if root == nil {
        return 
    }

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

    dfsInorder(root.Left, depth+1, res)

    (*res)[depth] = append((*res)[depth], root.Val)

    dfsInorder(root.Right, depth+1, res)
}

后序

func levelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    if root == nil {
        return res
    }
    dfsPostorder(root, 0, &res)
    return res
}

func dfsPostorder(root *TreeNode, depth int, res *[][]int) {
    if root == nil {
        return 
    }

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

    dfsPostorder(root.Left, depth+1, res)
    
    dfsPostorder(root.Right, depth+1, res)

    (*res)[depth] = append((*res)[depth], root.Val)
}

2.2 迭代+栈

Preorder

func levelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    if root == nil {
        return res
    }

    // Stack
    st := []NodeWithDepth{}
    cur := NodeWithDepth{Node: root, Depth: 0}

    // Preorder
    for cur.Node != nil || len(st) > 0 {
        for cur.Node != nil {
            if len(res) < cur.Depth+1 {
                res = append(res, []int{})
            }
            
            res[cur.Depth] = append(res[cur.Depth], cur.Node.Val)

            st = append(st, cur)
            cur = NodeWithDepth{Node: cur.Node.Left, Depth: cur.Depth+1}
        }

        cur, st = st[len(st)-1], st[:len(st)-1]
        
        cur = NodeWithDepth{Node: cur.Node.Right, Depth: cur.Depth+1}
    }

    return res
}

type NodeWithDepth struct {
    Node *TreeNode
    Depth int
}

Inorder

func levelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    if root == nil {
        return res
    }

    // Stack
    st := []NodeWithDepth{}
    cur := NodeWithDepth{Node: root, Depth: 0}

    // Inorder
    for cur.Node != nil || len(st) > 0 {
        for cur.Node != nil {
            if len(res) < cur.Depth+1 {
                res = append(res, []int{})
            }

            st = append(st, cur)
            cur = NodeWithDepth{Node: cur.Node.Left, Depth: cur.Depth+1}
        }

        cur, st = st[len(st)-1], st[:len(st)-1]
        res[cur.Depth] = append(res[cur.Depth], cur.Node.Val)

        cur = NodeWithDepth{Node: cur.Node.Right, Depth: cur.Depth+1}
    }

    return res
}

type NodeWithDepth struct {
    Node *TreeNode
    Depth int
}

Postorder

func levelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    if root == nil {
        return res
    }

    // Stack
    st := []NodeWithDepth{}
    cur := NodeWithDepth{Node: root, Depth: 0}
    prev := NodeWithDepth{}
    // Inorder
    for cur.Node != nil || len(st) > 0 {
        for cur.Node != nil {
            if len(res) < cur.Depth+1 {
                res = append(res, []int{})
            }
            
            st = append(st, cur)
            cur = NodeWithDepth{Node: cur.Node.Left, Depth: cur.Depth+1}
        }

        cur = st[len(st)-1]
        if cur.Node.Right != nil && cur.Node.Right != prev.Node {
            cur = NodeWithDepth{Node: cur.Node.Right, Depth: cur.Depth+1}
        } else {
            res[cur.Depth] = append(res[cur.Depth], cur.Node.Val)
            st = st[:len(st)-1]
            prev = cur
            cur = NodeWithDepth{}
        }
    }

    return res
}

type NodeWithDepth struct {
    Node *TreeNode
    Depth int
}

Reference

1. https://leetcode.cn/problems/binary-tree-level-order-traversal/solutions/241885/er-cha-shu-de-ceng-xu-bian-li-by-leetcode-solution/