层序遍历（Level-order Traversal）

一句话说明

层序遍历就是按层推进的 BFS，队列里装的始终是“下一批要处理的节点”。

（附件 bfs-layer-traversal.gif 未随站点发布）

Go 代码：分层输出

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
 
    queue := []*TreeNode{root}
    result := [][]int{}
 
    for len(queue) > 0 {
        size := len(queue)
        level := make([]int, 0, size)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            level = append(level, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        result = append(result, level)
    }
 
    return result
}

为什么要先固定 size

因为本层节点处理时会不断把下一层节点塞进队尾，不先记住当前长度，就分不清层与层。

Go 代码：右视图

func rightSideView(root *TreeNode) []int {
    if root == nil {
        return nil
    }
 
    queue := []*TreeNode{root}
    result := []int{}
 
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            if i == size-1 {
                result = append(result, node.Val)
            }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
 
    return result
}

相关主题

• 前序遍历
• 中序遍历
• 后序遍历
• 树算法

---

返回：树算法 | 算法学习导航