遞迴

解題思路

• 我們要找的最低公共祖先是一個節點，它同時是 p 和 q 的祖先，而且它的深度要盡量大。
• 我們用一個函數 來表示節點 的子樹中是否包含 p 或 q，如果包含就回傳 true，否則回傳 false。
• 我們以 top-down 的方式遍歷二元樹的每個節點，對於每個節點 ，我們判斷以下三個條件：
  • 的左子樹中包含 p 或 q
  • 的右子樹中包含 p 或 q
  • 自己就是 p 或 q
• 如果 滿足其中兩個或以上的條件，那麼 就是我們要找的最低公共祖先。
• 如果 只滿足其中一個條件，那麼我們就把這個條件的結果傳遞給 的父節點，讓它繼續判斷。
• 如果 一個條件都不滿足，那麼我們就回傳 false 給 的父節點。

跟一流的人才幹大事，享受成功進步的高級樂趣！
內推機會來啦！能與優秀的程式設計師共事，是特別痛快的事，因為厲害的工程師大神會刺激你想要迎頭趕上的上進心，尤其是一起討論解決方案時，他們會觸發你有更好的解決思維能力，彼此共同成長並且一起享受解謎與破關般的樂趣。 你一定聽得懂我在說甚麼感覺，趕快把握機會，動動手指投遞履歷吧！ 立即加入「面試讀書會」，和大家一起準備面試！

內推機會	加入讀書會 (邀請碼：7970)

程式

class Solution {
    fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
        return if (root == null || p == null || q == null) {
            null
        } else {
            find(root, p, q, n1Found = false, n2Found = false)
            lowest
        }
    }

    var lowest: TreeNode? = null
    fun find(root: TreeNode?, n1: TreeNode, n2: TreeNode, n1Found: Boolean, n2Found: Boolean): Pair<Boolean, Boolean> {
        if (root == null) return false to false
        else {
            val findN1 = (root == n1) || n1Found
            val findN2 = (root == n2) || n2Found
            val leftResult = if (root.left != null && (!findN1 || !findN2))
                find(root.left, n1, n2, n1Found, n2Found) else false to false
            val rightResult =
                if (root.right != null && (!findN1 || !findN2) && (!leftResult.first || !leftResult.second))
                    find(root.right, n1, n2, n1Found, n2Found) else false to false

            val result =
                (findN1 || leftResult.first || rightResult.first) to (findN2 || leftResult.second || rightResult.second)
            if (result.first && result.second && lowest == null) {
                lowest = root
            }
            return result
        }
    }
}

複雜度分析

• 時間複雜度:
  ，其中 是二元樹的節點數。這是因為我們要遍歷二元樹的每一個節點，而每個節點只會被遍歷一次。

• 空間複雜度:
  ，其中 是二元樹的節點數。因為我們要用一個堆疊來存儲遞迴呼叫的紀錄，堆疊的深度最多可以達到 ，所以空間複雜度是 。特別要注意的是，如果二元樹退化成一條鏈，那麼堆疊深度就會達到最大值 。

　更多 LeetCode 解答在此，一起來學習！

內推機會來啦！

跟一流的人才幹大事，享受成功進步的高級樂趣！

內推機會	加入讀書會 (邀請碼：7970)