主題
題目連結(jié)：
題目意譯：
給定一個(gè)二元樹，找到給定的兩個(gè)樹中之節(jié)點(diǎn)的最低共同祖先（Lowest Common Ancestor，LCA）。
根據(jù) LCA 於維基百科之定義：「最低共同祖先定義於兩節(jié)點(diǎn) p 和 q 上，而有一最低節(jié)點(diǎn) T 其有著 p 和 q 同作為其後代（這邊我們?cè)试S一個(gè)節(jié)點(diǎn)可為自己本身的後代）」。
限制：
樹中的節(jié)點(diǎn)數(shù)介於範(fàn)圍 [2, 10 ^ 5] 中。
-10 ^ 9 <= Node.val <= 10 ^ 9
所有 Node.val 皆相異。
p != q
p 和 q 皆會(huì)存在於樹中。
範(fàn)例測資：
Example 1:
輸入： root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出： 3
解釋： 節(jié)點(diǎn) 5 和 1 的 LCA 為 3。
Example 2:
輸入： root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出： 5
解釋： 節(jié)點(diǎn) 5 和 4 的 LCA 為 5，因?yàn)楦鶕?jù) LCA 的定義一個(gè)節(jié)點(diǎn)可以是自身的後代。
Example 3:
輸入： root = [1,2], p = 1, q = 2
輸出： 1
解題思維：
在深度優(yōu)先搜尋（Depth First Search，DFS）尋找 p 和 q 的過程中便可以順便求得 p 和 q 的 LCA：
假設(shè)目前的節(jié)點(diǎn)為 Q。
當(dāng)左右子樹各有著目標(biāo)節(jié)點(diǎn)（p 或 q）時(shí)，代表 p 和 q 各自分散在 Q 的左右子樹中。因此根據(jù) LCA 的定義，此時(shí) Q 即是 p 和 q 的 LCA；
如果左右子樹並不是兩者皆有目標(biāo)節(jié)點(diǎn)。但有其中一者含有目標(biāo)節(jié)點(diǎn)，且 Q 為目標(biāo)節(jié)點(diǎn)之一時(shí)，因?yàn)楣?jié)點(diǎn)可以為自身的後代，所以 Q 即為 LCA。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
