236.二叉樹的最近公共祖先

• 一定要仔細看提示，二叉樹數(shù)值不重復(fù)，意味著后序遍歷不會存在兩邊找到了同個元素的情況
• 本題需要進一步理解后序遍歷，可以認為后序遍歷在"深入"到每個子樹的最深層之后，才開始"回溯"并訪問節(jié)點。在某種意義上，這可以被視為從下往上的遍歷方式，但需要注意的是，它并不是簡單地按照樹的層級從下往上進行遍歷的。

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

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

輸入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出：3
解釋：節(jié)點 5 和節(jié)點 1 的最近公共祖先是節(jié)點 3 。

輸入：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é)點本身。

示例 3：
輸入：root = [1,2], p = 1, q = 2
輸出：1

思路

找最近公共祖先，也就是已知兩個節(jié)點，從下往上去找這兩個節(jié)點的最近公共祖先。

我們遍歷二叉樹的時候，不能從下往上去遍歷。但是我們的處理順序，是可以從下往上處理的。回溯的過程，實際上就是從底往上處理的過程。

針對某一個節(jié)點，左子樹出現(xiàn)了p或者右子樹出現(xiàn)了q，就把信息向上返回。實質(zhì)上就是后序遍歷的處理過程。

后序遍歷（左右中）就是天然的回溯過程，可以根據(jù)左右子樹的返回值，來處理中節(jié)點的邏輯。

思路就是后序遍歷，遇到p就返回，遇到q就返回，當某個節(jié)點左右子樹返回值都不為空的時候，這個節(jié)點就是最近的公共祖先。

• 注意，因為本題題目提示中說了二叉樹數(shù)值不重復(fù)，所以可以不用考慮兩邊找到了p/q同個元素的情況

完整版

• 注意p或者q其中一個本來就是公共祖先的情況。但是這種情況其實和后序遍歷處理邏輯是重合的。
• 遇到了p往上返回的時候，要注意這個題目并不是要求返回bool類型，而是要求返回最近公共祖先節(jié)點！因此，我們往上返回，應(yīng)該返回的是root本身

//后序遍歷，左子樹返回值不為空說明有p或q，右子樹同理
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //終止條件
        if(root==nullptr){
            return nullptr;
        }
        //后序，左右中
        //左
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        //右
        TreeNode* right = lowestCommonAncestor(root->right,p,q);
        //中，如果遇到了p/q就返回root，這道題目要求是root
        if(root==p||root==q){
            return root;
        }
        //如果都返回了就是最近公共祖先
        if(left!=nullptr&&right!=nullptr){
            return root;
        }
        //注意此處的邏輯！如果right存在left不存在，說明右子樹里面有p/q，需要返回right，而不是root！
        if(left==nullptr&&right!=nullptr){
            return right;
        }
        if(left!=nullptr&&right==nullptr){
            return left;
        }
        //如果以上全部不滿足，左是空右也是空
        return nullptr;
        
    }
};

后序遍歷的進一步理解

例如這個例子，后序遍歷（Post-Order Traversal）的總體順序是：(10的子樹) -> (4的子樹) -> 8

對于給定的二叉樹，我們可以按照后序遍歷的規(guī)則列出以下結(jié)果：

• 對于子樹10, 1, 7, 6, 5，后序遍歷的順序是：1 -> 6 -> 5 -> 7 -> 10.
• 對于子樹4, 15, 20，后序遍歷的順序是：15 -> 20 -> 4.
• 對于整個二叉樹，后序遍歷的順序是：(10的子樹) -> (4的子樹) -> 8。

所以，這棵樹的后序遍歷結(jié)果是：1, 6, 5, 7, 10, 15, 20, 4, 8。

后序遍歷并非從下往上遍歷，而是首先遍歷左孩子節(jié)點，然后遍歷右孩子節(jié)點，最后遍歷根節(jié)點。這個過程在每個子樹中都會被重復(fù)。

因此，可以認為后序遍歷在"深入"到每個子樹的最深層之后，才開始"回溯"并訪問節(jié)點。在某種意義上，這可以被視為從下往上的遍歷方式，但需要注意的是，它并不是簡單地按照樹的層級從下往上進行遍歷的。

這棵樹的前序和中序也補充一下：

前序遍歷：

• 對于子樹10, 1, 7, 6, 5，前序遍歷的順序是：10 -> 1 -> 7 -> 6 -> 5。
• 對于子樹4, 15, 20，前序遍歷的順序是：4 -> 15 -> 20。
• 對于整個二叉樹，前序遍歷的順序是：8 -> (10的子樹) -> (4的子樹)。

所以，這棵樹的前序遍歷結(jié)果是：8, 10, 1, 7, 6, 5, 4, 15, 20。

中序遍歷：

• 對于子樹10, 1, 7, 6, 5，中序遍歷的順序是：1 -> 10 -> 6 -> 7 -> 5。
• 對于子樹4, 15, 20，中序遍歷的順序是：15 -> 4 -> 20。
• 對于整個二叉樹，中序遍歷的順序是：(10的子樹) -> 8 -> (4的子樹)。

所以，這棵樹的中序遍歷結(jié)果是：1, 10, 6, 7, 5, 8, 15, 4, 20。

為什么左為空右不為空的時候return right

如果left為空，而right不為空，說明只有右子樹包含了這兩個指定節(jié)點之一或者右子樹包含了這兩個節(jié)點的最近公共祖先，所以返回right。反之，如果right為空，而left不為空，說明只有左子樹包含了這兩個指定節(jié)點之一或者左子樹包含了這兩個節(jié)點的最近公共祖先，所以返回left。

返回的結(jié)果最終都會向上層節(jié)點傳遞，直到找到最近公共祖先。

這個算法基于后序遍歷的原因是，我們需要檢查一個節(jié)點的左右子樹以確定該節(jié)點是否是兩個指定節(jié)點的公共祖先，所以必須等到遍歷了該節(jié)點的左右子樹之后才能做出決定，這符合后序遍歷的順序：左子樹 -> 右子樹 -> 根節(jié)點。也和后序遍歷進一步理解的本質(zhì)相同，也就是先深入左右子樹進行遍歷，再"回溯"回根節(jié)點。

這個邏輯是否包含p/q本身就是公共祖先的情況

如果p/q本身就是公共祖先，例如下圖的情況

如果是圖上情況，左子樹不是空的，右子樹是空，返回到7的時候，由于if(rootp||rootq)會判斷是不是本身和p/q相等，因此此時直接返回了7，其余部分又沒有p/q，因此直接一路向上返回。

這個邏輯的核心就在于，遇到了p/q直接把當前和p/q相等或滿足祖先條件的節(jié)點向上返回，并且當遇到左右有一個返回值的情況，繼續(xù)保留左邊的返回值。但還是會優(yōu)先返回和p/q相等的節(jié)點，包含了p/q本身是公共祖先的情況。

• 如果涉及到，中要根據(jù)左和右的結(jié)果來判斷，一定是后序遍歷。
• 將結(jié)果一層一層返回上去，涉及這個”回溯“的過程，一定是后序遍歷

235.二叉搜索樹的最近公共祖先

• 本題一定要注意思路的理解， 如果root的值在[p,q]之間，那么root一定是p和q的最近公共祖先！

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

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

例如，給定如下二叉搜索樹: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
輸出: 6 
解釋: 節(jié)點 2 和節(jié)點 8 的最近公共祖先是 6。

示例 2:

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

說明:

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

思路

本題要利用二叉搜索樹的特性，來找最近的公共祖先。

因為二叉搜索樹是有序樹，且順序為左子樹<根節(jié)點<右子樹。

• 如果根節(jié)點root大于p和q的值，說明公共祖先一定在左子樹里。
• 根節(jié)點root小于p和q的值，說明公共祖先一定在右子樹里。
• root的值在p和q之間，說明當前節(jié)點就是p和q的公共祖先。
  • 節(jié)點值在[p,q]之間，說明p一定在節(jié)點左子樹里，q一定在節(jié)點右子樹里。
  • 在這種情況下，無論是向左遍歷還是向右遍歷，總會錯過p/q其中的一個！只有當前節(jié)點，才能連接p和q！

因此，本題最重要的一點就是，如果節(jié)點root的值在p和q之間，那么節(jié)點root就是p和q的最近公共祖先！

可以畫二叉樹模擬一下。如果p/q分別在節(jié)點左子樹和右子樹里面，那么不管向哪個方向遍歷，都會錯過一個，不再是公共祖先了。也就是說后面不可能再有公共祖先了。

關(guān)于遍歷順序

這道題并不需要單獨考慮遍歷順序的問題，因為樹本身就是有序的，不需要處理中間節(jié)點所以沒有中間節(jié)點的邏輯，只要有一個左和一個右就可以了！

而且本題并不涉及到單調(diào)遞增的問題，不是一定要中序遍歷。并沒有中間節(jié)點邏輯。

遞歸法

最開始的寫法

• 這種寫法需要加很多if，代碼比較冗余，debug的情況比較多
• 二叉樹因為建立的時候比較麻煩，在IDE里debug不太方便，我們可以采用直接在力扣里面打印輸出的方式進行調(diào)試

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //搜索樹的有序性，按序排列
        if(root==nullptr){
            return nullptr;
        }
        TreeNode* right = nullptr;
        TreeNode* left = nullptr;

        //如果root小于p q 一定在右子樹里
        if(root->val<p->val&&root->val<q->val){
            right = lowestCommonAncestor(root->right,p,q);
            //cout<< righ->val <<endl;
        } 
        //如果root大于p q 一定在左子樹里
        if(root->val>p->val&&root->val>q->val){
            left = lowestCommonAncestor(root->left,p,q);
            //cout<< left->val <<endl;
        }
        if(root->val>p->val&&root->val<q->val){
            return root;
        }
        if(root->val>q->val&&root->val<p->val){
            cout<< root->val <<endl;
            return root;
        }
        if(root->val==p->val||root->val==q->val){
            //cout<< root->val <<endl;
            return root;
        }

       
        if(right!=nullptr&&left==nullptr){
            return right;
        }
        if(left!=nullptr&&right==nullptr){
            return left;
        }
        return nullptr;
    }
};

debug測試

這種較大的二叉樹比較難建，直接在力扣里面打印想看的中間結(jié)果就行

修改版

因為p和q的大小關(guān)系，原題目是沒有說的，所以我們最好把在PQ之間的情況放在else里面

• 核心點在于節(jié)點數(shù)值只要不為空，只有三種情況：小于p q，大于p q，其他情況全部都是我們要找的公共祖先！

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //這道題目并不需要處理中間節(jié)點，有左右就可以了
        if(root==nullptr){
            return nullptr;
        }
        //左右
        if(root->val<p->val&&root->val<q->val){
            //也可以寫在if里面，寫里面的話直接在里面返回
            TreeNode* right = lowestCommonAncestor(root->right,p,q);
            if(right!=nullptr){
                return right;
            }
        }
        if(root->val>p->val&&root->val>q->val){
            TreeNode* left = lowestCommonAncestor(root->left,p,q);
            if(left!=nullptr){
                return left;
            }
        }
        //夾在中間或者相等，這就是其余所有情況
        //直接return 不要寫在else里面否則會被判定沒有返回值
        return root;
    }
};

迭代法

最開始的寫法

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //都大于的時候向左遍歷
        while(root->val > p->val && root->val > q->val){
            root = root->left;
        }
        //都小于的時候向右遍歷
        while(root->val < p->val && root->val < q->val){
            root = root->right;
        }
        //找到最近公共祖先
        return root;
    }
};

為什么最開始這種寫法不行？

寫法在一個很長的用例上發(fā)生了報錯

這是因為整體寫法思路錯了，不能先一直往左找，再一直往右找，每走一層都要重新判斷往哪里走，因為可能先左后右再左。如果是上面的while寫法，就是左邊一直遍歷左子樹的左節(jié)點，但是錯過了左子樹的右節(jié)點！每一層都需要重新的判斷去左邊還是右邊。文章來源地址http://www.zghlxwxcb.cn/news/detail-483421.html

修改版

• 注意，這里可以寫while(1)，因為while里面是什么并不重要，總會跳出去！
• 最后還要寫返回值是因為函數(shù)必須有一個不在if語句內(nèi)的返回值，其實這里的返回值沒有意義，上面一定會返回

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //這里可以寫while(1)，因為while里面是什么并不重要，總會跳出去！
        //while(root!=nullptr)
        while(1)
        {
            if(root->val > p->val && root->val > q->val)
                root = root->left;
            else if(root->val < p->val && root->val < q->val)
                root = root->right;
            else
                return root;
        }
        //跳出while之后的返回值,其實這里隨便寫就行因為while里面一定會return
        return nullptr;
    }
};

到了這里，關(guān)于DAY23：二叉樹（十三）二叉樹的最近公共祖先+二叉搜索樹的最近公共祖先的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！