Diameter of Binary Tree

/**
 * 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;
}

import { describe, expect, it } from 'vitest';
import { diameterOfBinaryTree, TreeNode } from './solution';

describe('543. Diameter of Binary Tree', () => {
  function createTree(values: (number | null)[]): TreeNode | null {
    if (!values.length)
      return null;

    const root = new TreeNode(values[0] as number);
    const queue = [root];
    let i = 1;

    while (queue.length && i < values.length) {
      const node = queue.shift()!;

      // Left child
      if (i < values.length && values[i] !== null) {
        node.left = new TreeNode(values[i] as number);
        queue.push(node.left);
      }
      i++;

      // Right child
      if (i < values.length && values[i] !== null) {
        node.right = new TreeNode(values[i] as number);
        queue.push(node.right);
      }
      i++;
    }

    return root;
  }

  it('should handle example case 1', () => {
    const root = createTree([1, 2, 3, 4, 5]);
    expect(diameterOfBinaryTree(root)).toBe(3);
  });

  it('should handle example case 2', () => {
    const root = createTree([1, 2]);
    expect(diameterOfBinaryTree(root)).toBe(1);
  });

  it('should handle empty tree', () => {
    expect(diameterOfBinaryTree(null)).toBe(0);
  });

  it('should handle single node', () => {
    const root = createTree([1]);
    expect(diameterOfBinaryTree(root)).toBe(0);
  });

  it('should handle long path through root', () => {
    const root = createTree([1, 2, 3, 4, null, null, 5]);
    expect(diameterOfBinaryTree(root)).toBe(3);
  });
});

高度與直徑的關係

這個問題結合了深度計算和直徑計算的技巧。

核心洞察

對於任意節點，經過該節點的最長路徑長度 = 左子樹高度 + 右子樹高度

算法步驟

1. 遞歸計算高度：為每個節點計算其子樹高度
2. 更新直徑：在每個節點計算經過它的最長路徑
3. 維護最大值：使用全局變數追蹤最大直徑

複雜度分析

• 時間複雜度: O(n) - 每個節點訪問一次
• 空間複雜度: O(h) - h 是樹的高度，遞歸棧的深度

執行過程示例

以樹 [1,2,3,4,5] 為例：

    1
   / \
  2   3
 / \
4   5

計算過程：

1. 節點 4: 高度 = 1，直徑 = 0 + 0 = 0
2. 節點 5: 高度 = 1，直徑 = 0 + 0 = 0
3. 節點 2: 高度 = 2，直徑 = 1 + 1 = 2
4. 節點 3: 高度 = 1，直徑 = 0 + 0 = 0
5. 節點 1: 高度 = 3，直徑 = 2 + 1 = 3

最大直徑: 3（路徑：4-2-1-3 或 5-2-1-3）

邊界情況處理

1. 空樹: 直徑為 0
2. 單節點: 直徑為 0
3. 鏈狀樹: 直徑為節點數 - 1
4. 完全二叉樹: 直徑可能不經過根節點

重要的設計模式

這個問題展示了一個重要的模式：在遞歸過程中同時計算多個值。

每個遞歸函數調用都：

1. 計算當前節點的高度（返回值）
2. 更新全局的最大直徑（副作用）

類似問題的應用

1. 最遠葉子節點: 尋找距離最遠的兩個葉子
2. 樹的半徑: 從中心到最遠點的距離
3. 最長路徑和: 路徑上所有節點值的最大和
4. 最大路徑差: 路徑上最大值和最小值的差

優化版本

如果只需要返回直徑而不需要高度，可以將高度計算內嵌：

function diameterOptimized(root: TreeNode | null): number {
  let maxDiameter = 0;
  
  function dfs(node: TreeNode | null): number {
    if (!node) return 0;
    
    const left = dfs(node.left);
    const right = dfs(node.right);
    
    maxDiameter = Math.max(maxDiameter, left + right);
    
    return Math.max(left, right) + 1;
  }
  
  dfs(root);
  return maxDiameter;
}