[[419929]]

這道題目的看代碼比較簡單，而且好像也挺好理解的，但是如果把每一個細節理解到位，還是不容易的。

主要思考如下幾點：

• 如何從底向上遍歷?
• 遍歷整棵樹，還是遍歷局部樹?
• 如何把結果傳到根節點的?

這些問題都需要弄清楚，上來直接看代碼的話，是可能想不到這些細節的。

公共祖先問題，還是有難度的，初學者還是需要慢慢消化!

二叉樹的最近公共祖先

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

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

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

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

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

說明:

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

思路

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

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

回溯啊，二叉樹回溯的過程就是從低到上。

后序遍歷就是天然的回溯過程，最先處理的一定是葉子節點。

接下來就看如何判斷一個節點是節點q和節點p的公共公共祖先呢。

如果找到一個節點，發現左子樹出現結點p，右子樹出現節點q，或者 左子樹出現結點q，右子樹出現節點p，那么該節點就是節點p和q的最近公共祖先。

使用后序遍歷，回溯的過程，就是從低向上遍歷節點，一旦發現如何這個條件的節點，就是最近公共節點了。

遞歸三部曲：

• 確定遞歸函數返回值以及參數

需要遞歸函數返回值，來告訴我們是否找到節點q或者p，那么返回值為bool類型就可以了。

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

代碼如下：

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

• 確定終止條件

如果找到了 節點p或者q，或者遇到空節點，就返回。

代碼如下：

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

• 確定單層遞歸邏輯

值得注意的是 本題函數有返回值，是因為回溯的過程需要遞歸函數的返回值做判斷，但本題我們依然要遍歷樹的所有節點。

我們在二叉樹：遞歸函數究竟什么時候需要返回值，什么時候不要返回值?中說了 遞歸函數有返回值就是要遍歷某一條邊，但有返回值也要看如何處理返回值!

如果遞歸函數有返回值，如何區分要搜索一條邊，還是搜索整個樹呢?

搜索一條邊的寫法：

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

搜索整個樹寫法：

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

看出區別了沒?

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

那么為什么要遍歷整顆樹呢?直觀上來看，找到最近公共祖先，直接一路返回就可以了。

如圖：

.二叉樹的最近公共祖先

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

但事實上還要遍歷根節點右子樹(即使此時已經找到了目標節點了)，也就是圖中的節點4、15、20。

因為在如下代碼的后序遍歷中，如果想利用left和right做邏輯處理， 不能立刻返回，而是要等left與right邏輯處理完之后才能返回。

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

所以此時大家要知道我們要遍歷整棵樹。知道這一點，對本題就有一定深度的理解了。

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

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

如果left 和 right都不為空，說明此時root就是最近公共節點。這個比較好理解。

如果left為空，right不為空，就返回right，說明目標節點是通過right返回的，反之依然。

這里有的同學就理解不了了，為什么left為空，right不為空，目標節點通過right返回呢?

如圖：

二叉樹的最近公共祖先1

圖中節點10的左子樹返回null，右子樹返回目標值7，那么此時節點10的處理邏輯就是把右子樹的返回值(最近公共祖先7)返回上去!

這里點也很重要，可能刷過這道題目的同學，都不清楚結果究竟是如何從底層一層一層傳到頭結點的。

那么如果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; 
} 

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

二叉樹的最近公共祖先2

從圖中，大家可以看到，我們是如何回溯遍歷整顆二叉樹，將結果返回給頭結點的!

整體代碼如下：

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; 
        } 
 
    } 
}; 

稍加精簡，代碼如下：

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; 
    } 
}; 

總結

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

那么我給大家歸納如下三點：

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

在回溯的過程中，必然要遍歷整顆二叉樹，即使已經找到結果了，依然要把其他節點遍歷完，因為要使用遞歸函數的返回值(也就是代碼中的left和right)做邏輯判斷。

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

可以說這里每一步，都是有難度的，都需要對二叉樹，遞歸和回溯有一定的理解。

本題沒有給出迭代法，因為迭代法不適合模擬回溯的過程。理解遞歸的解法就夠了。

其他語言版本

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) {// 左右子樹分別找到了，說明此時的root就是要求的結果

return root;

}

if (left == null) {

return right;

}

return left;

}

}

// 代碼精簡版

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 //找到了節點p或者q，或者遇到空節點

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

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

if left and right: return root //中: left和right不為空，root就是最近公共節點

elif left and not right: return left //目標節點是通過left返回的

elif not left and right: return right //目標節點是通過right返回的

 

else: return None //沒找到