[[419929]]

這道題目的看代碼比較簡(jiǎn)單，而且好像也挺好理解的，但是如果把每一個(gè)細(xì)節(jié)理解到位，還是不容易的。

主要思考如下幾點(diǎn)：

• 如何從底向上遍歷?
• 遍歷整棵樹(shù)，還是遍歷局部樹(shù)?
• 如何把結(jié)果傳到根節(jié)點(diǎn)的?

這些問(wèn)題都需要弄清楚，上來(lái)直接看代碼的話(huà)，是可能想不到這些細(xì)節(jié)的。

公共祖先問(wèn)題，還是有難度的，初學(xué)者還是需要慢慢消化!

二叉樹(shù)的最近公共祖先

力扣鏈接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree

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

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

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

二叉樹(shù)的最近公共祖先

示例 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ù)中。

思路

遇到這個(gè)題目首先想的是要是能自底向上查找就好了，這樣就可以找到公共祖先了。

那么二叉樹(shù)如何可以自底向上查找呢?

回溯啊，二叉樹(shù)回溯的過(guò)程就是從低到上。

后序遍歷就是天然的回溯過(guò)程，最先處理的一定是葉子節(jié)點(diǎn)。

接下來(lái)就看如何判斷一個(gè)節(jié)點(diǎn)是節(jié)點(diǎn)q和節(jié)點(diǎn)p的公共公共祖先呢。

如果找到一個(gè)節(jié)點(diǎn)，發(fā)現(xiàn)左子樹(shù)出現(xiàn)結(jié)點(diǎn)p，右子樹(shù)出現(xiàn)節(jié)點(diǎn)q，或者 左子樹(shù)出現(xiàn)結(jié)點(diǎn)q，右子樹(shù)出現(xiàn)節(jié)點(diǎn)p，那么該節(jié)點(diǎn)就是節(jié)點(diǎn)p和q的最近公共祖先。

使用后序遍歷，回溯的過(guò)程，就是從低向上遍歷節(jié)點(diǎn)，一旦發(fā)現(xiàn)如何這個(gè)條件的節(jié)點(diǎn)，就是最近公共節(jié)點(diǎn)了。

遞歸三部曲：

• 確定遞歸函數(shù)返回值以及參數(shù)

需要遞歸函數(shù)返回值，來(lái)告訴我們是否找到節(jié)點(diǎn)q或者p，那么返回值為bool類(lèi)型就可以了。

但我們還要返回最近公共節(jié)點(diǎn)，可以利用上題目中返回值是TreeNode * ，那么如果遇到p或者q，就把q或者p返回，返回值不為空，就說(shuō)明找到了q或者p。

代碼如下：

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 

• 確定終止條件

如果找到了 節(jié)點(diǎn)p或者q，或者遇到空節(jié)點(diǎn)，就返回。

代碼如下：

if (root == q || root == p || root == NULL) return root; 

• 確定單層遞歸邏輯

值得注意的是 本題函數(shù)有返回值，是因?yàn)榛厮莸倪^(guò)程需要遞歸函數(shù)的返回值做判斷，但本題我們依然要遍歷樹(shù)的所有節(jié)點(diǎn)。

我們?cè)诙鏄?shù)：遞歸函數(shù)究竟什么時(shí)候需要返回值，什么時(shí)候不要返回值?中說(shuō)了 遞歸函數(shù)有返回值就是要遍歷某一條邊，但有返回值也要看如何處理返回值!

如果遞歸函數(shù)有返回值，如何區(qū)分要搜索一條邊，還是搜索整個(gè)樹(shù)呢?

搜索一條邊的寫(xiě)法：

if (遞歸函數(shù)(root->left)) return ; 
 
if (遞歸函數(shù)(root->right)) return ; 

搜索整個(gè)樹(shù)寫(xiě)法：

left = 遞歸函數(shù)(root->left); 
right = 遞歸函數(shù)(root->right); 
left與right的邏輯處理; 

看出區(qū)別了沒(méi)?

在遞歸函數(shù)有返回值的情況下：如果要搜索一條邊，遞歸函數(shù)返回值不為空的時(shí)候，立刻返回，如果搜索整個(gè)樹(shù)，直接用一個(gè)變量left、right接住返回值，這個(gè)left、right后序還有邏輯處理的需要，也就是后序遍歷中處理中間節(jié)點(diǎn)的邏輯(也是回溯)。

那么為什么要遍歷整顆樹(shù)呢?直觀(guān)上來(lái)看，找到最近公共祖先，直接一路返回就可以了。

如圖：

.二叉樹(shù)的最近公共祖先

就像圖中一樣直接返回7，多美滋滋。

但事實(shí)上還要遍歷根節(jié)點(diǎn)右子樹(shù)(即使此時(shí)已經(jīng)找到了目標(biāo)節(jié)點(diǎn)了)，也就是圖中的節(jié)點(diǎn)4、15、20。

因?yàn)樵谌缦麓a的后序遍歷中，如果想利用left和right做邏輯處理， 不能立刻返回，而是要等left與right邏輯處理完之后才能返回。

left = 遞歸函數(shù)(root->left); 
right = 遞歸函數(shù)(root->right); 
left與right的邏輯處理; 

所以此時(shí)大家要知道我們要遍歷整棵樹(shù)。知道這一點(diǎn)，對(duì)本題就有一定深度的理解了。

那么先用left和right接住左子樹(shù)和右子樹(shù)的返回值，代碼如下：

TreeNode* left = lowestCommonAncestor(root->left, p, q); 
TreeNode* right = lowestCommonAncestor(root->right, p, q); 

如果left 和 right都不為空，說(shuō)明此時(shí)root就是最近公共節(jié)點(diǎn)。這個(gè)比較好理解。

如果left為空，right不為空，就返回right，說(shuō)明目標(biāo)節(jié)點(diǎn)是通過(guò)right返回的，反之依然。

這里有的同學(xué)就理解不了了，為什么left為空，right不為空，目標(biāo)節(jié)點(diǎn)通過(guò)right返回呢?

如圖：

二叉樹(shù)的最近公共祖先1

圖中節(jié)點(diǎn)10的左子樹(shù)返回null，右子樹(shù)返回目標(biāo)值7，那么此時(shí)節(jié)點(diǎn)10的處理邏輯就是把右子樹(shù)的返回值(最近公共祖先7)返回上去!

這里點(diǎn)也很重要，可能刷過(guò)這道題目的同學(xué)，都不清楚結(jié)果究竟是如何從底層一層一層傳到頭結(jié)點(diǎn)的。

那么如果left和right都為空，則返回left或者right都是可以的，也就是返回空。

代碼如下：

if (left == NULL && right != NULL) return right; 
else if (left != NULL && right == NULL) return left; 
else  { //  (left == NULL && right == NULL) 
    return NULL; 
} 

那么尋找最小公共祖先，完整流程圖如下：

二叉樹(shù)的最近公共祖先2

從圖中，大家可以看到，我們是如何回溯遍歷整顆二叉樹(shù)，將結(jié)果返回給頭結(jié)點(diǎn)的!

整體代碼如下：

class Solution { 
public: 
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { 
        if (root == q || root == p || root == NULL) return root; 
        TreeNode* left = lowestCommonAncestor(root->left, p, q); 
        TreeNode* right = lowestCommonAncestor(root->right, p, q); 
        if (left != NULL && right != NULL) return root; 
 
        if (left == NULL && right != NULL) return right; 
        else if (left != NULL && right == NULL) return left; 
        else  { //  (left == NULL && right == NULL) 
            return NULL; 
        } 
 
    } 
}; 

稍加精簡(jiǎn)，代碼如下：

class Solution { 
public: 
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { 
        if (root == q || root == p || root == NULL) return root; 
        TreeNode* left = lowestCommonAncestor(root->left, p, q); 
        TreeNode* right = lowestCommonAncestor(root->right, p, q); 
        if (left != NULL && right != NULL) return root; 
        if (left == NULL) return right; 
        return left; 
    } 
}; 

總結(jié)

這道題目刷過(guò)的同學(xué)未必真正了解這里面回溯的過(guò)程，以及結(jié)果是如何一層一層傳上去的。

那么我給大家歸納如下三點(diǎn)：

求最小公共祖先，需要從底向上遍歷，那么二叉樹(shù)，只能通過(guò)后序遍歷(即：回溯)實(shí)現(xiàn)從低向上的遍歷方式。

在回溯的過(guò)程中，必然要遍歷整顆二叉樹(shù)，即使已經(jīng)找到結(jié)果了，依然要把其他節(jié)點(diǎn)遍歷完，因?yàn)橐褂眠f歸函數(shù)的返回值(也就是代碼中的left和right)做邏輯判斷。

要理解如果返回值left為空，right不為空為什么要返回right，為什么可以用返回right傳給上一層結(jié)果。

可以說(shuō)這里每一步，都是有難度的，都需要對(duì)二叉樹(shù)，遞歸和回溯有一定的理解。

本題沒(méi)有給出迭代法，因?yàn)榈ú贿m合模擬回溯的過(guò)程。理解遞歸的解法就夠了。

其他語(yǔ)言版本

Java

class Solution {

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

return lowestCommonAncestor1(root, p, q);

}

public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {

if (root == null || root == p || root == q) {

return root;

}

TreeNode left = lowestCommonAncestor1(root.left, p, q);

TreeNode right = lowestCommonAncestor1(root.right, p, q);

if (left != null && right != null) {// 左右子樹(shù)分別找到了，說(shuō)明此時(shí)的root就是要求的結(jié)果

return root;

}

if (left == null) {

return right;

}

return left;

}

}

// 代碼精簡(jiǎn)版

class Solution {

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if (root == null || root.val == p.val ||root.val == q.val) return root;

TreeNode left = lowestCommonAncestor(root.left,p,q);

TreeNode right = lowestCommonAncestor(root.right,p,q);

if (left != null && right != null) return root;

else if (left == null && right != null) return right;

else if (left != null && right == null) return left;

else return null;

}

}

Python

//遞歸

class Solution:

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

if not root or root == p or root == q: return root //找到了節(jié)點(diǎn)p或者q，或者遇到空節(jié)點(diǎn)

left = self.lowestCommonAncestor(root.left,p,q) //左

right = self.lowestCommonAncestor(root.right,p,q) //右

if left and right: return root //中: left和right不為空，root就是最近公共節(jié)點(diǎn)

elif left and not right: return left //目標(biāo)節(jié)點(diǎn)是通過(guò)left返回的

elif not left and right: return right //目標(biāo)節(jié)點(diǎn)是通過(guò)right返回的

else: return None //沒(méi)找到