題目敘述
題目會給定一顆二元樹的根結點Root node，和這棵樹中的任意兩個節點p, q。
請找出p, q 在這棵二元數裡面的最接近公共祖先節點是誰?
最接近的公共節點: 就是p, q兩個節點從下往上走，第一個交會的節點。
測試範例
Example 1:
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.
節點5和節點1的公最接近公共節點是 節點3
Example 2:
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.
節點5和節點4的公最接近公共節點是 節點5
Example 3:
Input: root = [1,2], p = 1, q = 2
Output: 1
節點1和節點2的公最接近公共節點是 節點1
演算法 討論可能的情況，並且分類。使用DFS深度優先搜索
假如從樹根Root node開始往下搜索的話，會有下列幾種情況。
- 空節點、或 空樹，一定不可能是別人的共同祖先，返回None。
- 現在這個節點剛好是p 或者 剛好是q，返回當下這個節點。
- p, q 都落在右子樹(root.right)裡面，遞回去右子樹裡面找。
- p, q 都落在左子樹(root.left)裡面，遞回去左子樹裡面找。
- p, q 剛好其中一個在左子樹裡面，另一個在右子樹裡面，那麼，當下的root node剛好就是最接近公共祖先節點。
最接近的公共節點: 就是p, q兩個節點從下往上走，第一個交會的節點。
程式碼 討論可能的情況，並且分類。使用DFS深度優先搜索
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root:
# Empty tree or empty node
return None
if root is p or root is q:
# Current node is either p or q
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if not left:
# Both p, q reside in right subtree
return right
elif not right:
# Both p, q reside in left subtree
return left
else:
# One reside in left subtree, the other reside in right subtree
# Current root node is Lowest Common Ancestor of (p, q)
return root
複雜度分析 討論可能的情況，並且分類。使用DFS深度優先搜索
時間複雜度:
從根結點開始，探索整顆樹，每個結點最多拜訪一次，所需時間為O(n)。
空間複雜度:
從根結點開始，探索整顆樹，遞迴深度最深為n，發生在整顆樹向左歪斜或向右歪斜的時候，所需recursion call stack最深為O(n)。
