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)。