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

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

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

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

例如，給定如下二叉樹(shù): 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)本身。 

說(shuō)明:

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

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

解題思路：

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

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

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