從LeetCode學演算法

0235. Lowest Common Ancestor of a Binary Search Tree (Easy)

(當然，Medium的拍手也可以多拍幾下啦XD)

Question

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself ).”

Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]

Example 1

1
2
3
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2

1
2
3
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Note:

All of the nodes’ values will be unique.
p and q are different and both values will exist in the BST.

分析/解題

給定一個二元搜尋樹及其中兩個不同的節點，
試找出它們的最近共同祖先(LCA)。

題目有標註說一個節點可以視作自己的後裔(descendant)，
這點會有影響，還請留意。

那麼，我們如何尋找這個最近共同祖先呢？
首先要知道，這是一棵二元搜尋樹，假設這個LCA的節點叫作L好了，
兩個節點分別叫p跟q，那麼我們可以考慮以下幾個狀況：

如果L是p或q其中之一的話，先遇到誰，就代表誰是那個LCA 。
(因為先遇到的節點會是後面的那個節點的祖先)
如果L不是p或q其中之一 的話，L的値的範圍必在p.val和q.val之間 ，
也就是說兩者會位在L的不同側的子樹。
(即p.val < L.val < q.val或p.val > L.val > q.val)

如果從root開始判斷的話，就可以分成幾種情況：

root的値和p或q的值相等 => ** 直接回傳root** (p或q就是L)
root的値在p和q的值的範圍之內 => ** 直接回傳root**
(即p.val < L.val < q.val 或p.val > L.val > q.val )
p和q的値都小於 root的值 => 往下找root.left 的狀況遞迴
p和q的値都大於 root的值 => 往下找root.right 的狀況遞迴

也就是說，最終總會找到L是p或q之一 ，或者L能將兩個節點拆成兩邊 。
於是我們可以輕鬆解出這個題目，在Python的部分，
除了要留意a < b < c這種形式是Python才能用的，Java不接受以外，
這邊在Java的解答中要提供一個較簡潔的解法。

仔細思考的話，我們可以發現1, 2其實可以看作一件事情：
root.val - p.val和root.val - q.val的關係。
當符合1. 的時候，上面的兩個式子會有一個等於0 ；
當符合2. 的時候，上面的兩個式子會一正一負 。
所以兩者相乘 時，符合1.跟2.的條件的狀況下，
結果會<=0 (或<1，因為值是int)。

同時，當不符1.且不符2.時，由於p, q已經確定是同邊 了，
只需要拿p來比較即可，不用再去比較q。

根據上面的推導我們可以寫成Java的答案版本。
同時，由於每次遞迴都只有動到root所指向的節點，
所以我們也可以很簡單地將其改動成迭代的解法，
由於不需call stack，總體速度有可能會有些許的加快。

Java

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(Worst case: O(N)/O(N) (如果節點都在同一邊)
平衡樹的話最大會走到整個深度的節點，是O(logN))
(用迭代解的話，因為不用call stack，空間複雜度為O(1))

「用相乘的方法會有什麼副作用？」
(在有限定變數是int的狀況下，相乘有機會導致溢位 ，所以如果這題的測試資料刁鑽一點的話，請不要用相乘的，一組一組判斷就好。)

相似及延伸

1.0236. Lowest Common Ancestor of a Binary Tree (如果這棵樹只是二元樹 而非二元搜尋樹呢？)

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~