leetcode hot100【LeetCode 104. 二叉树的最大深度】java实现

LeetCode 104. 二叉树的最大深度

题目描述

给定一个二叉树，找出其最大深度。

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

示例 1：

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

示例 2：

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

示例 3：

输入：root = []
输出：0

提示： 树的高度不会超过 10^4 节点。

Java 实现解法

方法一：递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

方法二：迭代

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int depth = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            depth++;  // 每遍历一层，深度加 1

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();  // 从队列中取出节点
                if (node.left != null) queue.add(node.left);  // 加入左子节点
                if (node.right != null) queue.add(node.right);  // 加入右子节点
            }
        }
        return depth;
    }
}

解题思路

方法一:

• 递归方法：
  • 如果当前节点 root 为空，返回深度为 0。
  • 递归地计算左子树和右子树的最大深度。
  • 返回两个子树中较大深度加 1（当前节点的深度）。

这种方法的时间复杂度是 O(n)，其中 n 是树中节点的数量，因为每个节点恰好被访问一次。空间复杂度是 O(h)，其中 h 是树的高度，这取决于递归调用的栈空间，在最坏情况下（树完全不平衡，如链状结构），空间复杂度为 O(n)。

方法二:

• 迭代方法：
  • 使用一个队列来实现层次遍历（也称为广度优先搜索，BFS）。
  • 如果根节点为空，直接返回深度为 0。
  • 初始化一个队列并将根节点加入队列，同时初始化深度为 0。
  • 进入循环，直到队列为空，表示所有节点都被访问过。
  • 在每次循环中，计算当前层的节点数，然后遍历这些节点，将它们的子节点加入队列。
  • 每遍历完一层，深度加一。
    这种方法的时间复杂度同样是 O(n)，其中 n 是树中节点的数量，因为每个节点恰好被访问一次。空间复杂度是 O(m)，其中 m 是树的宽度，即队列中存储的最大节点数，这取决于树的最宽层。在最宽的树（所有非叶子节点都具有两个子节点）中，空间复杂度为 O(n/2)，即 O(n)。