本文轉(zhuǎn)載自微信公眾號「三分鐘學(xué)前端」，作者sisterAn。轉(zhuǎn)載本文請聯(lián)系三分鐘學(xué)前端公眾號。

關(guān)于樹基礎(chǔ)看這里：適合初學(xué)者的樹

給定一個(gè)二叉樹, 找到該樹中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先。

百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個(gè)結(jié)點(diǎn) p、q，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大(一個(gè)節(jié)點(diǎn)也可以是它自己的祖先)。”

例如，給定如下二叉樹: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 
輸出: 3 
解釋: 節(jié)點(diǎn) 5 和節(jié)點(diǎn) 1 的最近公共祖先是節(jié)點(diǎn) 3。 

示例 2:

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 
輸出: 5 
解釋: 節(jié)點(diǎn) 5 和節(jié)點(diǎn) 4 的最近公共祖先是節(jié)點(diǎn) 5。因?yàn)楦鶕?jù)定義最近公共祖先節(jié)點(diǎn)可以為節(jié)點(diǎn)本身。 

說明:

• 所有節(jié)點(diǎn)的值都是唯一的。
• p、q 為不同節(jié)點(diǎn)且均存在于給定的二叉樹中。

解答：遞歸實(shí)現(xiàn)

解題思路：

如果樹為空樹或 p 、 q 中任一節(jié)點(diǎn)為根節(jié)點(diǎn)，那么 p 、 q 的最近公共節(jié)點(diǎn)為根節(jié)點(diǎn)

如果不是，即二叉樹不為空樹，且 p 、 q 為非根節(jié)點(diǎn)，則遞歸遍歷左右子樹，獲取左右子樹的最近公共祖先，

• 如果 p 、 q 節(jié)點(diǎn)在左右子樹的最近公共祖先都存在，說明 p 、 q 節(jié)點(diǎn)分布在左右子樹的根節(jié)點(diǎn)上，此時(shí)二叉樹的最近公共祖先為 root
• 若 p 、 q 節(jié)點(diǎn)在左子樹最近公共祖先為空，那 p 、q 節(jié)點(diǎn)位于左子樹上，最終二叉樹的最近公共祖先為右子樹上 p 、q 節(jié)點(diǎn)的最近公共祖先
• 若 p 、 q 節(jié)點(diǎn)在右子樹最近公共祖先為空，同左子樹 p 、 q 節(jié)點(diǎn)的最近公共祖先為空一樣的判定邏輯
• 如果 p 、 q 節(jié)點(diǎn)在左右子樹的最近公共祖先都為空，則返回 null

代碼實(shí)現(xiàn)：

const lowestCommonAncestor = function(root, p, q) { 
    if(root == null || root == p || root == q) return root 
    const left = lowestCommonAncestor(root.left, p, q) 
    const right = lowestCommonAncestor(root.right, p, q) 
    if(left === null) return right 
    if(right === null) return left 
    return root 
}; 

復(fù)雜度分析：

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(n)