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 实现解法
方法一：递归
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;}
}
方法二：迭代
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;Queue<TreeNode> queue = new LinkedList<>();queue.add(root);int depth = 0;while (!queue.isEmpty()) {int size = queue.size();depth++; // 每遍历一层，深度加 1for (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)。
