基本資訊

• 難度： Easy
• 網址： https://leetcode.com/problems/diameter-of-binary-tree/

題意

給予一個二元樹的根節點 root ，請求出樹的「直徑」。而這邊的直徑就是代表其中兩個節點有可能的「在長距離」。而這個最長距離也有可能不會穿過 root 節點。

思維

看到要找樹的深度，就是要 go deep 。這時候就可以先試試看 DFS (深度優先搜尋) 和 backtracking 。

Backtracking

而對於 backtracking 的 subroutine ，我們必須定義結束遞迴呼叫的條件。

停止條件

• 當傳入的 root 為零，就回傳 0 不繼續執行

走訪方式

• 用遞迴走訪左右節點，取得各自的樹高

因此可以拿左右的樹高做兩件事情

1. 算出這個節點出發的直徑和目前最大直徑比較，有大於的話則更新最大直徑。
2. 我們只關心最大的樹高，因此找出最大樹高並回傳。

最大直徑

因為不能確定在樹的哪邊會拿到最大值，因此會在遞迴的過程之外需要有個變數來暫存這個值，並在走訪過程中不斷的檢查和更新她。

程式碼

class Solution {
    func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
        var result = 0
        height(root, &result)
        return result
    }

    /// Backtracking
    @discardableResult
    func height(_ root: TreeNode?,_ result: inout Int) -> Int {
        if root == nil { return 0 }

        let left = height(root?.left, &result)
        let right = height(root?.right, &result)

        result = max(result, left + right)
        return max(left, right) + 1
    }
}

執行結果

• Runtime: 19 ms (Beats 95.26%)
• Memory: 14.6 MB (Beats 25.30%)

複雜度分析

令 n 為節點數

結語

以上，就是今天的 LeetCode in Swift ，

如果有什麼問題和回饋歡迎留言一起討論，今天就到這裡，明天見！