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

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

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

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

例如，給定如下二叉樹: 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é)點 5 和節(jié)點 1 的最近公共祖先是節(jié)點 3。 

示例 2:

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

說明:

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

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

解題思路：

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

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

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

代碼實現(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ù)雜度分析：

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

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