從LeetCode學演算法

0236. Lowest Common Ancestor of a Binary Tree (Medium)

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

Question

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

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 the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

Example 1

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

Example 2

1
2
3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, 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 binary tree.

分析/解題

給定一棵二元樹，試找出樹中兩個給定的節點的最低共同祖先(LCA)。
整棵樹的節點值均不同，且兩個節點p, q是不同的節點，
且會存在於此樹上。

由於不同於之前的0235題，這題是二元樹而非二元搜尋樹，
所以我們於此喪失了可以透過比大小來決定要往哪個方向走的可能。
那麼怎麼辦呢？

對於兩個節點的最低共同祖先來說，有一個特性是絕對肯定的，
就是以下3點必然會恰好成立2點 ：
1. 節點自己是p或q
2. 節點的左子樹有p或q
3. 節點的右子樹有p或q

1, 2和1, 3應該很直觀，就不多作解釋了，
這邊有一點很重要的是，當共同祖先不是p或q 的時候，
如果p和q都分布在同一邊的子樹，那它就不會是最低共同祖先 ，
因為我們還可以再往下找更低的共同祖先。
所以1不成立的時候，2, 3都必須要成立才行 ，
這樣才能符合最低的特性。

我們可以運用DFS 的方式來確認一個節點的左子樹/右子樹是否符合特性，
並且同時判斷該節點是否是p或q之一 ，
這樣一來，只要三者成立兩點 的時候，就表示我們找到目標了，
可以將答案記錄下來。

所以只要將整棵樹遍歷過一次，最後回傳記錄下來的答案即可。
實作上，我們將1當作成立，0當作不成立，
那麼整個DFS的過程就是在找三個結果相加等於2。

Java

Python部分基本一致，只是三元運算是由if else來寫的。

Python

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

「時間/空間複雜度？」
(O(N)/O(N)，因為要考慮到最糟的情況，同時遞迴會產生call stack )

「能否給出迭代解？」
(原題的Solution處有給出來，請參照看看XD，簡單來說，
就是分別使用stack記錄p跟q的祖先節點，最後回頭找最底層的那個祖先。)
(但因為使用stack的關係，空間複雜度依舊會是O(N) )

相似及延伸

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

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