104. 二叉树的最大深度
题目描述
输入二叉树的根节点 root，求这棵树的最大深度。
最大深度指从根出发、走到离根最远的叶子，这条路径一共经过多少个节点（根和叶子都算）。
空树的深度为 0。树用层序数组表示，null 代表空位。
示例 1
输入：root = [3,9,20,null,null,15,7] 输出：3
解释：最长路径如 3 -> 20 -> 15，共 3 个节点。
示例 2
输入：root = [1,null,2] 输出：2
解释：路径 1 -> 2 有 2 个节点。
数据范围
- 节点总数在
[0, 10^4]之间。 -100 <= Node.val <= 100
解题思路：递归深度优先搜索
递归求左右子树深度，取较大值加一。
为什么正确
每次调用返回当前子树的准确最大深度。
复杂度分析
时间 O(n)，递归栈 O(h)；h 为树高，最坏可为 n；Python 递归受解释器递归深度限制，深链树应改用显式栈。
易错点
深度按节点数计算，叶子深度是 1，空节点才是 0。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def maxDepth(self, root):
if root is None:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
};func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}var maxDepth = function(root) {
if (root === null) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};function maxDepth(root: TreeNode | null): number {
if (root === null) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};其他解法
递归写法最短，空间随树高变化；广度优先搜索按层计数，空间随层宽变化，并且没有递归深度限制。
解法 2：广度优先搜索 时间 O(n)，空间 O(w)
用队列按层遍历。每轮先固定队列长度，把这一层的节点全部弹出，并把它们的子节点入队。每处理完一层，深度加一，队列为空时的深度就是答案。
没有递归，深链树也不会栈溢出。辅助空间取决于最大层宽 w，宽而矮的树比递归更占空间。
from collections import deque
class Solution:
def maxDepth(self, root):
if root is None:
return 0
queue = deque([root])
depth = 0
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
depth += 1
return depthclass Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
Deque<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
int depth = 0;
while (!queue.isEmpty()) {
for (int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
depth++;
}
return depth;
}
}class Solution {
public:
int maxDepth(TreeNode* root) {
if (!root) return 0;
queue<TreeNode*> q;
q.push(root);
int depth = 0;
while (!q.empty()) {
for (int i = q.size(); i > 0; i--) {
TreeNode* node = q.front(); q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
depth++;
}
return depth;
}
};func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
queue := []*TreeNode{root}
depth := 0
for len(queue) > 0 {
for i := len(queue); i > 0; i-- {
node := queue[0]
queue = queue[1:]
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
depth++
}
return depth
}var maxDepth = function(root) {
if (!root) return 0;
let queue = [root];
let depth = 0;
while (queue.length) {
const next = [];
for (const node of queue) {
if (node.left) next.push(node.left);
if (node.right) next.push(node.right);
}
queue = next;
depth++;
}
return depth;
};function maxDepth(root: TreeNode | null): number {
if (!root) return 0;
let queue: TreeNode[] = [root];
let depth = 0;
while (queue.length) {
const next: TreeNode[] = [];
for (const node of queue) {
if (node.left) next.push(node.left);
if (node.right) next.push(node.right);
}
queue = next;
depth++;
}
return depth;
};