Maximum Depth of Binary Tree
•--
Find the maximum depth of a binary tree using recursive traversal
Find the maximum number of nodes along the longest path from root to leaf
問題描述
給定一個二叉樹 root，返回其最大深度。
二叉樹的 最大深度 是指從根節點到最遠葉子節點的最長路徑上的節點數。
範例
輸入：root = [3,9,20,null,null,15,7]
輸出：3
輸入：root = [1,null,2]
輸出：2
限制條件
- 樹中節點的數量在
[0, 10⁴]範圍內 -100 <= Node.val <= 100
解題思路
### 遞歸分解 樹的最大深度 = max(左子樹深度, 右子樹深度) + 1
### 基礎情況 空節點的深度為 0
### 遞歸計算 分別計算左右子樹深度，取最大值加 1
解決方案
typescript
/**
* Definition for a binary tree node.
*/
export class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = val === undefined ? 0 : val;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
}
}
export function maxDepth(root: TreeNode | null): number {
// Base case: depth of empty node is 0
if (!root)
return 0;
// Recursively calculate depth of left and right subtrees
const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);
// Return the maximum depth + 1 (current node)
return Math.max(leftDepth, rightDepth) + 1;
}