二叉树层次遍历

4分钟阅读

来源：go-interview / Algorithm

树的层次遍历（Level Order Traversal）是一种遍历树的算法，按照树的层次从上到下、从左到右依次访问树的每一个节点。通常使用广度优先搜索（BFS）的思想来实现这种遍历。

层次遍历的算法实现

层次遍历的实现通常使用队列（Queue）数据结构，因为队列可以保证先入先出的顺序，从而保证节点按层次的顺序被访问。

算法步骤

  1. 初始化队列：首先，将树的根节点加入队列。
  2. 循环遍历：只要队列不为空，就从队列的头部取出一个节点，访问该节点。
  3. 访问子节点：将被访问节点的左子节点和右子节点（如果有）依次加入队列。
  4. 重复步骤 2 和 3，直到队列为空为止。

示例代码

以下是用 Go 语言实现的二叉树层次遍历代码：

package main
 
import (
    "fmt"
)
 
// 定义二叉树节点
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}
 
// 层次遍历函数
func levelOrder(root *TreeNode) [][]int {
    var result [][]int
    if root == nil {
        return result
    }
    
    // 创建队列，并将根节点加入队列
    queue := []*TreeNode{root}
    
    // 当队列不为空时
    for len(queue) > 0 {
        // 获取当前层次节点的数量
        levelSize := len(queue)
        var currentLevel []int
        
        // 访问当前层次的所有节点
        for i := 0; i < levelSize; i++ {
            // 从队列中取出节点
            node := queue[0]
            queue = queue[1:]
            
            // 将节点的值加入当前层次结果中
            currentLevel = append(currentLevel, node.Val)
            
            // 将左右子节点加入队列
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        
        // 将当前层次结果加入最终结果
        result = append(result, currentLevel)
    }
    
    return result
}
 
// 主函数
func main() {
    // 构造一棵二叉树
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Left = &TreeNode{Val: 4}
    root.Left.Right = &TreeNode{Val: 5}
    root.Right.Left = &TreeNode{Val: 6}
    root.Right.Right = &TreeNode{Val: 7}
    
    // 层次遍历并输出结果
    result := levelOrder(root)
    fmt.Println(result) // [[1], [2 3], [4 5 6 7]]
}

运行结果

假设构建的二叉树如下：

        1
       / \
      2   3
     / \ / \
    4  5 6  7

层次遍历的输出结果是：[[1], [2 3], [4 5 6 7]]。

复杂度分析

  • 时间复杂度：O(n)，其中 n 是树中节点的数量。因为每个节点都被访问一次。
  • 空间复杂度：O(n)，主要取决于队列的大小，最坏情况下，队列中需要存储一整层的节点。

这种遍历方式非常适合用于逐层处理树结构的问题，如查找树的最浅深度、按层次打印树的节点等。

反向链接