Diameter of Binary Tree
•--
Find the longest path between any two nodes in a binary tree
Calculate the length of the longest path between any two nodes in a binary tree
問題描述
給定一個二叉樹 root，返回其 直徑 的長度。
二叉樹的 直徑 是指樹中任意兩個節點之間最長路徑的 長度。這條路徑可能經過也可能不經過根節點。
兩節點之間路徑的長度 是由它們之間邊的數目表示。
範例
輸入：root = [1,2,3,4,5]
輸出：3
解釋：直徑路徑是 [4,2,1,3] 或者 [5,2,1,3]，長度為 3
輸入：root = [1,2]
輸出：1
限制條件
- 樹中節點數的範圍是
[1, 10⁴] -100 <= Node.val <= 100
解題思路
### 直徑的定義 直徑 = 左子樹高度 + 右子樹高度
### 遞歸計算高度 在計算高度的同時更新最大直徑
### 全局維護最大值 使用全局變數追蹤最大直徑
解決方案
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 diameterOfBinaryTree(root: TreeNode | null): number {
// Track the maximum diameter
let maxDiameter = 0;
// Recursively calculate each node's height while updating max diameter
function calculateHeight(node: TreeNode | null): number {
// Base case: height of empty node is 0
if (node === null)
return 0;
// Recursively calculate left and right subtree heights
const leftHeight = calculateHeight(node.left);
const rightHeight = calculateHeight(node.right);
// Update maximum diameter (left subtree height + right subtree height)
maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
// Return current node's height (max of left/right subtree + 1)
return Math.max(leftHeight, rightHeight) + 1;
}
calculateHeight(root);
return maxDiameter;
}