[[420656]]

利用二叉搜索樹的特性，會被如此簡單的迭代法感動到痛哭流涕!

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

題目鏈接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

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

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

例如，給定如下二叉搜索樹: 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, 因為根據定義最近公共祖先節(jié)點可以為節(jié)點本身。

說明:

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

思路

做過二叉樹：公共祖先問題題目的同學應該知道，利用回溯從底向上搜索，遇到一個節(jié)點的左子樹里有p，右子樹里有q，那么當前節(jié)點就是最近公共祖先。

那么本題是二叉搜索樹，二叉搜索樹是有序的，那得好好利用一下這個特點。

在有序樹里，如果判斷一個節(jié)點的左子樹里有p，右子樹里有q呢?

其實只要從上到下遍歷的時候，cur節(jié)點是數值在[p, q]區(qū)間中則說明該節(jié)點cur就是最近公共祖先了。

理解這一點，本題就很好解了。

和二叉樹：公共祖先問題不同，普通二叉樹求最近公共祖先需要使用回溯，從底向上來查找，二叉搜索樹就不用了，因為搜索樹有序(相當于自帶方向)，那么只要從上向下遍歷就可以了。

那么我們可以采用前序遍歷(其實這里沒有中節(jié)點的處理邏輯，遍歷順序無所謂了)。

如圖所示：p為節(jié)點3，q為節(jié)點5

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

可以看出直接按照指定的方向，就可以找到節(jié)點4，為最近公共祖先，而且不需要遍歷整棵樹，找到結果直接返回!

遞歸法

遞歸三部曲如下：

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

參數就是當前節(jié)點，以及兩個結點 p、q。

返回值是要返回最近公共祖先，所以是TreeNode * 。

代碼如下：

TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) 

• 確定終止條件

遇到空返回就可以了，代碼如下：

if (cur == NULL) return cur; 

其實都不需要這個終止條件，因為題目中說了p、q 為不同節(jié)點且均存在于給定的二叉搜索樹中。也就是說一定會找到公共祖先的，所以并不存在遇到空的情況。

• 確定單層遞歸的邏輯

在遍歷二叉搜索樹的時候就是尋找區(qū)間[p->val, q->val](注意這里是左閉又閉)

那么如果 cur->val 大于 p->val，同時 cur->val 大于q->val，那么就應該向左遍歷(說明目標區(qū)間在左子樹上)。

需要注意的是此時不知道p和q誰大，所以兩個都要判斷

代碼如下：

if (cur->val > p->val && cur->val > q->val) { 
    TreeNode* left = traversal(cur->left, p, q); 
    if (left != NULL) { 
        return left; 
    } 
} 

細心的同學會發(fā)現，在這里調用遞歸函數的地方，把遞歸函數的返回值left，直接return。

在二叉樹：公共祖先問題中，如果遞歸函數有返回值，如何區(qū)分要搜索一條邊，還是搜索整個樹。

搜索一條邊的寫法：

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

搜索整個樹寫法：

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

本題就是標準的搜索一條邊的寫法，遇到遞歸函數的返回值，如果不為空，立刻返回。

如果 cur->val 小于 p->val，同時 cur->val 小于 q->val，那么就應該向右遍歷(目標區(qū)間在右子樹)。

if (cur->val < p->val && cur->val < q->val) { 
    TreeNode* right = traversal(cur->right, p, q); 
    if (right != NULL) { 
        return right; 
    } 
} 

剩下的情況，就是cur節(jié)點在區(qū)間(p->val <= cur->val && cur->val <= q->val)或者 (q->val <= cur->val && cur->val <= p->val)中，那么cur就是最近公共祖先了，直接返回cur。

代碼如下：

return cur; 

那么整體遞歸代碼如下:

class Solution { 
private: 
    TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) { 
        if (cur == NULL) return cur; 
                                                        // 中 
        if (cur->val > p->val && cur->val > q->val) {   // 左 
            TreeNode* left = traversal(cur->left, p, q); 
            if (left != NULL) { 
                return left; 
            } 
        } 
 
        if (cur->val < p->val && cur->val < q->val) {   // 右 
            TreeNode* right = traversal(cur->right, p, q); 
            if (right != NULL) { 
                return right; 
            } 
        } 
        return cur; 
    } 
public: 
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { 
        return traversal(root, p, q); 
    } 
}; 

精簡后代碼如下：

class Solution { 
public: 
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { 
        if (root->val > p->val && root->val > q->val) { 
            return lowestCommonAncestor(root->left, p, q); 
        } else if (root->val < p->val && root->val < q->val) { 
            return lowestCommonAncestor(root->right, p, q); 
        } else return root; 
    } 
}; 

迭代法

對于二叉搜索樹的迭代法，大家應該在二叉樹：二叉搜索樹登場!就了解了。

利用其有序性，迭代的方式還是比較簡單的，解題思路在遞歸中已經分析了。

迭代代碼如下：

class Solution { 
public: 
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { 
        while(root) { 
            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; 
        } 
        return NULL; 
    } 
}; 

靈魂拷問：是不是又被簡單的迭代法感動到痛哭流涕?

總結

對于二叉搜索樹的最近祖先問題，其實要比普通二叉樹公共祖先問題簡單的多。

不用使用回溯，二叉搜索樹自帶方向性，可以方便的從上向下查找目標區(qū)間，遇到目標區(qū)間內的節(jié)點，直接返回。

最后給出了對應的迭代法，二叉搜索樹的迭代法甚至比遞歸更容易理解，也是因為其有序性(自帶方向性)，按照目標區(qū)間找就行了。

其他語言版本

Java

迭代法：

class Solution { 
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
        while (true) { 
            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 { 
                break; 
            } 
        } 
        return root; 
    } 
} 

Python

遞歸法：

class Solution: 
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': 
        if not root: return root  //中 
        if root.val >p.val and root.val > q.val: 
            return self.lowestCommonAncestor(root.left,p,q)  //左 
        elif root.val < p.val and root.val < q.val: 
            return self.lowestCommonAncestor(root.right,p,q)  //右 
        else: return root