104.二叉树的最大深度

LeetCode LeetCode 热题100 树 深度优先搜索 广度优先搜索 二叉树
发布时间 :
字数:1.8k 阅读 : 评论:
  1. 104.二叉树的最大深度
    1. 104.1 题目
    2. 104.2 题解
      1. 方法一：递归
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：迭代（层序遍历）
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 104.3 代码
    4. 104.4 运行结果

104.二叉树的最大深度

104.1 题目

给定一个二叉树 root，返回其最大深度。

二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

提示：

  • 树中节点的数量在 [0, 10^4] 区间内。
  • -100 <= Node.val <= 100

104.2 题解

方法一：递归

思路

二叉树的最大深度等于「左子树的最大深度」和「右子树的最大深度」中的较大值，再加 1（当前节点本身）。这是一个典型的分治思想。

递归逻辑：

  1. 终止条件：节点为空，返回深度 0
  2. 递归计算左右子树的深度
  3. 取较大值后加 1

举个例子：

      3
     / \
    9  20
      /  \
     15   7

计算过程：
- 节点9：左子树深度0，右子树深度0，max(0,0)+1 = 1
- 节点15：左子树深度0，右子树深度0，max(0,0)+1 = 1
- 节点7：左子树深度0，右子树深度0，max(0,0)+1 = 1
- 节点20：左子树深度1，右子树深度1，max(1,1)+1 = 2
- 节点3：左子树深度1，右子树深度2，max(1,2)+1 = 3

复杂度分析

  • 时间复杂度：O(n)，每个节点被访问一次
  • 空间复杂度：O(h)，递归栈深度为树的高度，最坏情况为 O(n)

代码

// 方法一：递归
// 先判空，递归计算左右子树的最大深度，返回较大者加1
static int MaxDepth1(TreeNode root)
{
    // 如果当前节点为空（即递归到叶子节点的下一层），返回深度为0
    if (root == null) return 0;
    // 使用 Math.Max 函数计算左右子树的最大深度，递归调用 MaxDepth1 函数
    // 1 + MaxDepth1(root.left) 表示左子树的深度加上当前节点的深度
    // 1 + MaxDepth1(root.right) 表示右子树的深度加上当前节点的深度
    // Math.Max 用于取两者中的较大值
    return Math.Max(MaxDepth1(root.left), MaxDepth1(root.right)) + 1;
}

方法二：迭代（层序遍历）

思路

用队列进行层序遍历，逐层统计节点数。每遍历完一层，深度加 1。

具体步骤：

  1. 根节点入队，深度初始化为 0
  2. 记录当前层的节点数 levelSize
  3. 依次出队这些节点，并将它们的非空子节点入队
  4. 一层处理完毕后，深度加 1
  5. 队列为空时，深度即为答案

举个例子：

      3
     / \
    9  20
      /  \
     15   7

遍历过程：
- 第1层：队列 [3]，出队3，入队9、20，depth=1
- 第2层：队列 [9, 20]，出队9、20，入队15、7，depth=2
- 第3层：队列 [15, 7]，出队15、7，无子节点，depth=3
- 队列为空，返回 depth=3

复杂度分析

  • 时间复杂度：O(n)，每个节点被访问一次
  • 空间复杂度：O(w)，队列最多存储一层的节点，w 为树的最大宽度，最坏情况为 O(n)

代码

// 方法二：迭代（层序遍历）
// 使用队列进行层序遍历，把每层的节点丢到队列中，下次循环出队把左右子节点丢进去，记录每一层的节点数和深度
static int MaxDepth2(TreeNode root)
{
    // 如果当前节点为空（即递归到叶子节点的下一层），返回深度为0
    if (root == null)
    {
        return 0;
    }

    // 创建一个队列，用于层序遍历二叉树
    Queue<TreeNode> queue = new Queue<TreeNode>();
    // 将根节点入队
    queue.Enqueue(root);

    // 初始化深度为0
    int depth = 0;

    // 使用 while 循环进行层序遍历
    while (queue.Count > 0)
    {
        // 记录当前层的节点数
        int levelSize = queue.Count;

        // 遍历当前层的所有节点
        for (int i = 0; i < levelSize; i++)
        {
            // 出队一个节点
            TreeNode node = queue.Dequeue();

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

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

        // 每完成一层的遍历，深度加1
        depth++;
    }

    // 返回二叉树的深度
    return depth;
}

104.3 代码

using System;

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

    public TreeNode(int x)
    {
        val = x;
    }
}

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

        // 给定一个二叉树 root ，返回其最大深度。
        // 二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

        // 示例 1：
        // 输入：root = [3,9,20,null,null,15,7]
        // 输出：3

        // 示例 2：
        // 输入：root = [1,null,2]
        // 输出：2

        // 提示：
        // 树中节点的数量在 [0, 104] 区间内。
        // -100 <= Node.val <= 100

        #endregion

        #region 测试

        // 示例 1
        TreeNode root1 = new TreeNode(3)
        {
            left = new TreeNode(9),
            right = new TreeNode(20)
            {
                left = new TreeNode(15),
                right = new TreeNode(7)
            }
        };

        int result1 = MaxDepth1(root1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");

        int result1_2 = MaxDepth2(root1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        TreeNode root2 = new TreeNode(1)
        {
            right = new TreeNode(2)
        };

        int result2 = MaxDepth1(root2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");

        int result2_2 = MaxDepth2(root2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：递归
    // 先判空，递归计算左右子树的最大深度，返回较大者加1
    static int MaxDepth1(TreeNode root)
    {
        // 如果当前节点为空（即递归到叶子节点的下一层），返回深度为0
        if (root == null) return 0;
        // 使用 Math.Max 函数计算左右子树的最大深度，递归调用 MaxDepth1 函数
        // 1 + MaxDepth1(root.left) 表示左子树的深度加上当前节点的深度
        // 1 + MaxDepth1(root.right) 表示右子树的深度加上当前节点的深度
        // Math.Max 用于取两者中的较大值
        return Math.Max(MaxDepth1(root.left), MaxDepth1(root.right)) + 1;
    }

    // 方法二：迭代（层序遍历）
    // 使用队列进行层序遍历，把每层的节点丢到队列中，下次循环出队把左右子节点丢进去，记录每一层的节点数和深度
    static int MaxDepth2(TreeNode root)
    {
        // 如果当前节点为空（即递归到叶子节点的下一层），返回深度为0
        if (root == null)
        {
            return 0;
        }

        // 创建一个队列，用于层序遍历二叉树
        Queue<TreeNode> queue = new Queue<TreeNode>();
        // 将根节点入队
        queue.Enqueue(root);
    
        // 初始化深度为0
        int depth = 0;

        // 使用 while 循环进行层序遍历
        while (queue.Count > 0)
        {
            // 记录当前层的节点数
            int levelSize = queue.Count;

            // 遍历当前层的所有节点
            for (int i = 0; i < levelSize; i++)
            {
                // 出队一个节点
                TreeNode node = queue.Dequeue();

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

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

            // 每完成一层的遍历，深度加1
            depth++;
        }

        // 返回二叉树的深度
        return depth;
    }



    #endregion
}

104.4 运行结果

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

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏