102.二叉树的层序遍历

LeetCode LeetCode 广度优先搜索 二叉树 热题100 队列
发布时间 :
字数:2.1k 阅读 : 评论:
  1. 102.二叉树的层序遍历
    1. 102.1 题目
    2. 102.2 题解
      1. 方法一：迭代（层序遍历/BFS，使用队列）
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：递归（深度优先搜索/DFS，记录层数）
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 102.3 代码
    4. 102.4 运行结果

102.二叉树的层序遍历

102.1 题目

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

102.2 题解

方法一：迭代（层序遍历/BFS，使用队列）

思路

层序遍历就是一层一层地访问节点，用队列实现。

关键技巧：在每轮循环开始时，记录当前队列的大小，这个大小就是当前层的节点数。然后只处理这么多个节点，就能把每一层分开。

具体步骤：

  1. 根节点入队
  2. 记录当前层的节点数 levelSize
  3. 遍历当前层的所有节点：出队、收集值、左右子节点入队
  4. 每处理完一层，把这一层的值列表加入结果

举个例子：

      3
     / \
    9  20
      /  \
     15   7

队列变化：
- 第1层：队列[3]，出队3，入队9、20 → 结果[[3]]
- 第2层：队列[9,20]，出队9、20，入队15、7 → 结果[[3],[9,20]]
- 第3层：队列[15,7]，出队15、7 → 结果[[3],[9,20],[15,7]]

复杂度分析

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

代码

// 方法一：迭代（层序遍历/BFS，使用队列）
// 使用队列进行层序遍历，记录每一层的节点数，遍历当前层节点并收集值，同时将下一层节点入队
static IList<IList<int>> LevelOrderIterative(TreeNode root)
{
    IList<IList<int>> result = new List<IList<int>>();
    // 如果根节点为空，直接返回空列表
    if (root == null) return result;

    Queue<TreeNode> queue = new Queue<TreeNode>();
    queue.Enqueue(root);

    // 循环处理队列中的节点
    while (queue.Count > 0)
    {
        // 记录当前层的节点数
        int levelSize = queue.Count;
        // 用于存储当前层的节点值
        List<int> currentLevel = new List<int>();

        // 遍历当前层的所有节点
        for (int i = 0; i < levelSize; i++)
        {
            TreeNode node = queue.Dequeue();
            // 将当前节点值加入当前层列表
            currentLevel.Add(node.val);

            // 如果左子节点不为空，将左子节点入队
            if (node.left != null)
            {
                queue.Enqueue(node.left);
            }

            // 如果右子节点不为空，将右子节点入队
            if (node.right != null)
            {
                queue.Enqueue(node.right);
            }
        }

        // 将当前层的节点值列表加入结果
        result.Add(currentLevel);
    }

    return result;
}

方法二：递归（深度优先搜索/DFS，记录层数）

思路

用 DFS 也能做层序遍历，关键是记录当前节点在第几层。

递归时传入层数 level，把节点值加入对应层的列表。如果 level == result.Count，说明需要新增一层的列表。

举个例子：

      3
     / \
    9  20
      /  \
     15   7

DFS访问顺序：3 → 9 → 20 → 15 → 7
- 访问3，level=0，result=[[3]]
- 访问9，level=1，result=[[3],[9]]
- 访问20，level=1，result=[[3],[9,20]]
- 访问15，level=2，result=[[3],[9,20],[15]]
- 访问7，level=2，result=[[3],[9,20],[15,7]]

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)，递归栈

代码

// 方法二：递归（深度优先搜索/DFS，记录层数）
// 通过递归遍历二叉树，记录当前节点的层数，将节点值加入对应层数的列表中
static IList<IList<int>> LevelOrderRecursive(TreeNode root)
{
    IList<IList<int>> result = new List<IList<int>>();
    // 调用辅助递归方法，初始层数为0
    LevelOrderHelper(root, 0, result);
    return result;
}

// 递归辅助方法：node为当前节点，level为当前层数，result为结果列表
static void LevelOrderHelper(TreeNode node, int level, IList<IList<int>> result)
{
    // 如果当前节点为空，直接返回
    if (node == null) return;

    // 如果当前层数等于结果列表的数量，说明需要新增一层的列表
    if (level == result.Count)
    {
        result.Add(new List<int>());
    }

    // 将当前节点值加入对应层数的列表
    result[level].Add(node.val);

    // 递归遍历左子树，层数+1
    LevelOrderHelper(node.left, level + 1, result);
    // 递归遍历右子树，层数+1
    LevelOrderHelper(node.right, level + 1, result);
}

102.3 代码

using System;
using System.Collections.Generic;

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Program
{
    static void Main()
    {
        #region 题目

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

        #endregion

        #region 测试

        // 示例 1
        TreeNode root1 = new TreeNode(3,
            new TreeNode(9),
            new TreeNode(20, new TreeNode(15), new TreeNode(7)));
        IList<IList<int>> result1 = LevelOrderIterative(root1);
        Console.WriteLine($"示例1 迭代 方法 输出：{FormatList(result1)}");
        IList<IList<int>> result1_2 = LevelOrderRecursive(root1);
        Console.WriteLine($"示例1 递归 方法 输出：{FormatList(result1_2)}");

        // 示例 2
        TreeNode root2 = new TreeNode(1);
        IList<IList<int>> result2 = LevelOrderIterative(root2);
        Console.WriteLine($"示例2 迭代 方法 输出：{FormatList(result2)}");
        IList<IList<int>> result2_2 = LevelOrderRecursive(root2);
        Console.WriteLine($"示例2 递归 方法 输出：{FormatList(result2_2)}");

        // 示例 3
        TreeNode root3 = null;
        IList<IList<int>> result3 = LevelOrderIterative(root3);
        Console.WriteLine($"示例3 迭代 方法 输出：{FormatList(result3)}");
        IList<IList<int>> result3_2 = LevelOrderRecursive(root3);
        Console.WriteLine($"示例3 递归 方法 输出：{FormatList(result3_2)}");

        #endregion
    }

    #region 辅助方法

    // 辅助方法：格式化层序遍历结果为字符串，方便输出
    static string FormatList(IList<IList<int>> list)
    {
        if (list == null || list.Count == 0) return "[]";
        List<string> levelStrings = new List<string>();
        foreach (var level in list)
        {
            levelStrings.Add($"[{string.Join(",", level)}]");
        }

        return $"[{string.Join(",", levelStrings)}]";
    }

    #endregion

    #region 答案

    // 方法一：迭代（层序遍历/BFS，使用队列）
    // 使用队列进行层序遍历，记录每一层的节点数，遍历当前层节点并收集值，同时将下一层节点入队
    static IList<IList<int>> LevelOrderIterative(TreeNode root)
    {
        IList<IList<int>> result = new List<IList<int>>();
        // 如果根节点为空，直接返回空列表
        if (root == null) return result;

        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);

        // 循环处理队列中的节点
        while (queue.Count > 0)
        {
            // 记录当前层的节点数
            int levelSize = queue.Count;
            // 用于存储当前层的节点值
            List<int> currentLevel = new List<int>();

            // 遍历当前层的所有节点
            for (int i = 0; i < levelSize; i++)
            {
                TreeNode node = queue.Dequeue();
                // 将当前节点值加入当前层列表
                currentLevel.Add(node.val);

                // 如果左子节点不为空，将左子节点入队
                if (node.left != null)
                {
                    queue.Enqueue(node.left);
                }

                // 如果右子节点不为空，将右子节点入队
                if (node.right != null)
                {
                    queue.Enqueue(node.right);
                }
            }

            // 将当前层的节点值列表加入结果
            result.Add(currentLevel);
        }

        return result;
    }

    // 方法二：递归（深度优先搜索/DFS，记录层数）
    // 通过递归遍历二叉树，记录当前节点的层数，将节点值加入对应层数的列表中
    static IList<IList<int>> LevelOrderRecursive(TreeNode root)
    {
        IList<IList<int>> result = new List<IList<int>>();
        // 调用辅助递归方法，初始层数为0
        LevelOrderHelper(root, 0, result);
        return result;
    }

    // 递归辅助方法：node为当前节点，level为当前层数，result为结果列表
    static void LevelOrderHelper(TreeNode node, int level, IList<IList<int>> result)
    {
        // 如果当前节点为空，直接返回
        if (node == null) return;

        // 如果当前层数等于结果列表的数量，说明需要新增一层的列表
        if (level == result.Count)
        {
            result.Add(new List<int>());
        }

        // 将当前节点值加入对应层数的列表
        result[level].Add(node.val);

        // 递归遍历左子树，层数+1
        LevelOrderHelper(node.left, level + 1, result);
        // 递归遍历右子树，层数+1
        LevelOrderHelper(node.right, level + 1, result);
    }

    #endregion
}

102.4 运行结果

示例1 迭代 方法 输出：[[3],[9,20],[15,7]]
示例1 递归 方法 输出：[[3],[9,20],[15,7]]
示例2 迭代 方法 输出：[[1]]
示例2 递归 方法 输出：[[1]]
示例3 迭代 方法 输出：[]
示例3 递归 方法 输出：[]
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏