二叉樹的最近公共祖先
這道題目的看代碼比較簡單，而且好像也挺好理解的，但是如果把每一個細節理解到位，還是不容易的。
主要思考如下幾點：
- 如何從底向上遍歷?
- 遍歷整棵樹，還是遍歷局部樹?
- 如何把結果傳到根節點的?
這些問題都需要弄清楚，上來直接看代碼的話，是可能想不到這些細節的。
公共祖先問題，還是有難度的，初學者還是需要慢慢消化!
二叉樹的最近公共祖先
力扣鏈接：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 //沒找到
