二叉搜索樹的公共祖先問題！
利用二叉搜索樹的特性，會(huì)被如此簡(jiǎn)單的迭代法感動(dòng)到痛哭流涕!
二叉搜索樹的最近公共祖先
題目鏈接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
給定一個(gè)二叉搜索樹, 找到該樹中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先。
百度百科中最近公共祖先的定義為：“對(duì)于有根樹 T 的兩個(gè)結(jié)點(diǎn) p、q，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大(一個(gè)節(jié)點(diǎn)也可以是它自己的祖先)。”
例如，給定如下二叉搜索樹: 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é)點(diǎn) 2 和節(jié)點(diǎn) 8 的最近公共祖先是 6。
示例 2:
- 輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
- 輸出: 2
- 解釋: 節(jié)點(diǎn) 2 和節(jié)點(diǎn) 4 的最近公共祖先是 2, 因?yàn)楦鶕?jù)定義最近公共祖先節(jié)點(diǎn)可以為節(jié)點(diǎn)本身。
說明:
- 所有節(jié)點(diǎn)的值都是唯一的。
- p、q 為不同節(jié)點(diǎn)且均存在于給定的二叉搜索樹中。
思路
做過二叉樹：公共祖先問題題目的同學(xué)應(yīng)該知道，利用回溯從底向上搜索，遇到一個(gè)節(jié)點(diǎn)的左子樹里有p，右子樹里有q，那么當(dāng)前節(jié)點(diǎn)就是最近公共祖先。
那么本題是二叉搜索樹，二叉搜索樹是有序的，那得好好利用一下這個(gè)特點(diǎn)。
在有序樹里，如果判斷一個(gè)節(jié)點(diǎn)的左子樹里有p，右子樹里有q呢?
其實(shí)只要從上到下遍歷的時(shí)候，cur節(jié)點(diǎn)是數(shù)值在[p, q]區(qū)間中則說明該節(jié)點(diǎn)cur就是最近公共祖先了。
理解這一點(diǎn)，本題就很好解了。
和二叉樹：公共祖先問題不同，普通二叉樹求最近公共祖先需要使用回溯，從底向上來查找，二叉搜索樹就不用了，因?yàn)樗阉鳂溆行?相當(dāng)于自帶方向)，那么只要從上向下遍歷就可以了。
那么我們可以采用前序遍歷(其實(shí)這里沒有中節(jié)點(diǎn)的處理邏輯，遍歷順序無所謂了)。
如圖所示：p為節(jié)點(diǎn)3，q為節(jié)點(diǎn)5
二叉搜索樹的最近公共祖先
可以看出直接按照指定的方向，就可以找到節(jié)點(diǎn)4，為最近公共祖先，而且不需要遍歷整棵樹，找到結(jié)果直接返回!
遞歸法
遞歸三部曲如下：
- 確定遞歸函數(shù)返回值以及參數(shù)
參數(shù)就是當(dāng)前節(jié)點(diǎn)，以及兩個(gè)結(jié)點(diǎn) p、q。
返回值是要返回最近公共祖先，所以是TreeNode * 。
代碼如下：
- TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q)
- 確定終止條件
遇到空返回就可以了，代碼如下：
- if (cur == NULL) return cur;
其實(shí)都不需要這個(gè)終止條件，因?yàn)轭}目中說了p、q 為不同節(jié)點(diǎn)且均存在于給定的二叉搜索樹中。也就是說一定會(huì)找到公共祖先的，所以并不存在遇到空的情況。
- 確定單層遞歸的邏輯
在遍歷二叉搜索樹的時(shí)候就是尋找區(qū)間[p->val, q->val](注意這里是左閉又閉)
那么如果 cur->val 大于 p->val，同時(shí) cur->val 大于q->val，那么就應(yīng)該向左遍歷(說明目標(biāo)區(qū)間在左子樹上)。
需要注意的是此時(shí)不知道p和q誰大，所以兩個(gè)都要判斷
代碼如下：
- if (cur->val > p->val && cur->val > q->val) {
- TreeNode* left = traversal(cur->left, p, q);
- if (left != NULL) {
- return left;
- }
- }
細(xì)心的同學(xué)會(huì)發(fā)現(xiàn)，在這里調(diào)用遞歸函數(shù)的地方，把遞歸函數(shù)的返回值left，直接return。
在二叉樹：公共祖先問題中，如果遞歸函數(shù)有返回值，如何區(qū)分要搜索一條邊，還是搜索整個(gè)樹。
搜索一條邊的寫法：
- if (遞歸函數(shù)(root->left)) return ;
- if (遞歸函數(shù)(root->right)) return ;
搜索整個(gè)樹寫法：
- left = 遞歸函數(shù)(root->left);
- right = 遞歸函數(shù)(root->right);
- left與right的邏輯處理;
本題就是標(biāo)準(zhǔn)的搜索一條邊的寫法，遇到遞歸函數(shù)的返回值，如果不為空，立刻返回。
如果 cur->val 小于 p->val，同時(shí) cur->val 小于 q->val，那么就應(yīng)該向右遍歷(目標(biāo)區(qū)間在右子樹)。
- if (cur->val < p->val && cur->val < q->val) {
- TreeNode* right = traversal(cur->right, p, q);
- if (right != NULL) {
- return right;
- }
- }
剩下的情況，就是cur節(jié)點(diǎn)在區(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);
- }
- };
精簡(jiǎn)后代碼如下：
- 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;
- }
- };
迭代法
對(duì)于二叉搜索樹的迭代法，大家應(yīng)該在二叉樹：二叉搜索樹登場(chǎng)!就了解了。
利用其有序性，迭代的方式還是比較簡(jiǎn)單的，解題思路在遞歸中已經(jīng)分析了。
迭代代碼如下：
- 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;
- }
- };
靈魂拷問：是不是又被簡(jiǎn)單的迭代法感動(dòng)到痛哭流涕?
總結(jié)
對(duì)于二叉搜索樹的最近祖先問題，其實(shí)要比普通二叉樹公共祖先問題簡(jiǎn)單的多。
不用使用回溯，二叉搜索樹自帶方向性，可以方便的從上向下查找目標(biāo)區(qū)間，遇到目標(biāo)區(qū)間內(nèi)的節(jié)點(diǎn)，直接返回。
最后給出了對(duì)應(yīng)的迭代法，二叉搜索樹的迭代法甚至比遞歸更容易理解，也是因?yàn)槠溆行蛐?自帶方向性)，按照目標(biāo)區(qū)間找就行了。
其他語(yǔ)言版本
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
