543. Diameter of Binary Tree

Easy

Description

給定一棵二元樹，求其直徑。直徑定義為任意兩個節點之間最長路徑的邊數。此路徑不一定經過根節點。

Example:

Input: root = [1,2,3,4,5] Output: 3 (路徑為 4 -> 2 -> 1 -> 3 或 5 -> 2 -> 1 -> 3)

Intuition#

對每個節點，經過它的最長路徑 = 左子樹高度 + 右子樹高度；全域追蹤最大值。

直徑不一定經過根節點，所以要檢查每個節點
在計算高度的同時順便更新直徑，一次 DFS 即可完成

Approaches#

1: Brute Force（每個節點分別計算）#

概念: 對每個節點計算其左右子樹高度之和，取最大值。每次計算高度需要遍歷子樹。
時間複雜度: O(n^2)，最差情況下每個節點都要重新計算高度
空間複雜度: O(n)

class Solution {
    fun diameterOfBinaryTree(root: TreeNode?): Int {
        if (root == null) return 0
        val throughRoot = height(root.left) + height(root.right)
        val leftDiameter = diameterOfBinaryTree(root.left)
        val rightDiameter = diameterOfBinaryTree(root.right)
        return maxOf(throughRoot, leftDiameter, rightDiameter)
    }

    private fun height(node: TreeNode?): Int {
        if (node == null) return 0
        return 1 + maxOf(height(node.left), height(node.right))
    }
}

⭐ 2: DFS 同時計算高度與直徑#

概念: 在計算每個節點高度的遞迴過程中，同時更新全域直徑變數
時間複雜度: O(n)
空間複雜度: O(h)

class Solution {
    private var diameter = 0

    fun diameterOfBinaryTree(root: TreeNode?): Int {
        diameter = 0
        height(root)
        return diameter
    }

    private fun height(node: TreeNode?): Int {
        if (node == null) return 0
        val left = height(node.left)
        val right = height(node.right)
        diameter = maxOf(diameter, left + right)
        return 1 + maxOf(left, right)
    }
}

🔑 Takeaways#

Pattern: 在遞迴中利用「回傳值」和「全域變數」同時追蹤兩個不同的量
關鍵技巧: 很多樹的最佳化問題（直徑、最大路徑和）都可以在計算高度時順便求解，避免重複遍歷