算法力扣刷题记录 五十七【236. 二叉树的最近公共祖先】和【235. 二叉搜索树的最近公共祖先】

前言

公共祖先解决。二叉树和二叉搜索树条件下的最近公共祖先。
二叉树篇继续。

---

一、【236. 二叉树的最近公共祖先】题目阅读

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
1
2
3

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
1
2
3

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1
1
2

提示：

树中节点数目在范围 [2, 10^5] 内。
-10^9 <= Node.val <= 10^9
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。
1
2
3
4
5

---

二、【236. 二叉树的最近公共祖先】题目解答

弯路（第一次做题时，可能的想法）

1. 二叉树习惯用递归法解决问题，那么需要确定遍历顺序和重复执行的递归逻辑。
2. 本题是二叉树，需要求最近公共祖先，那么父节点应该是最后遍历。所以尝试遍历顺序：后序——左右中。
3. 如何找到统一执行的规律呢？回到中间节点需要处理什么逻辑？

• 受前几节二叉搜索树中序遍历整合到数组中，那么此处遍历结果数组得到之后，看p,q哪个在前，选择在前面的p或者q？可是无法区分自己是祖先的情况。（不正确）

正确思路获取

参考思路链接

1. 确定后序遍历，因为需要从节点p,q向上退出父节点，所以中间节点最后处理。（左右中）
2. 返回中间节点什么信息？判断左子树中是否存在p或q，判断右子树中是否存在p或q：

• 如果左子树有p，右子树有q；左子树有q，右子树有p。此时返回中间节点（最近公共祖先）。

• 如果一边子树为空，另一边子树有p或q之一。此时返回left或者right，即子树返回的节点。注意：这里不能返回中间节点。会把最近公共祖先丢掉。
  

• 如果两边子树都为空，说明该中间节点的左右子树不包含p和q。向上返回空。

3. 所以递归函数返回值：TreeNode* 类型；
4. 递归函数终止条件：如果cur是空，return空。如果cur->val是p或q，return cur。

• 两个终止条件：第一个空判断可以容易想到。
• 如果第二个终止条件没有想到：影响吗？可以拯救：在中间逻辑先判断该节点是否为p或q，如果是，那么return cur；如果不是，走第2.点的逻辑。
• 所以第二个终止条件放到中间节点之前，更简单。

5. 总结：左右中：先看左右子树能向中间节点返回什么信息——空节点说明不包含p和q；非空节点说明有p或有q或有p和q。注意，中间节点应该真正返回什么，有的是cur（自身），有的是left或right.

代码实现【二叉树的最近公共祖先+递归法】

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return nullptr;
        if(root->val == q->val || root->val == p->val) return root;

        //左
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        //右
        TreeNode* right = lowestCommonAncestor(root->right,p,q);
        //中节点
        if(!left && !right) return nullptr;//说明该子树没有p也没有q
        else if(!left && right) return right;//一定要返回right。而不是root
        else if(!right && left) return left;//一定要返回left。而不是root。
        else return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

补充说明【细节】

补充思路中没提及的情况2：自身是祖先——以上代码在哪一处包含

1. p和q不是包含关系，情况1：肯定是某个中间节点的两边子树；
2. p和q是包含关系，无论谁包含谁——情况2：如示例2.在某个节点的同一个子树内。if(root->val == q->val || root->val == p->val) return root;将包含者向上返回。（不用深入找q了。）
   

拯救：没想到终止条件2时

• 可以这样想：先看自己是不是目标，如果是，返回自己。如果不是，看左右子树有没有包含。
• 看left和right之前先确定自己不是目标。else return root。
• 所以把终止条件2放到上面更好一点。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return nullptr;
        //没想到在这里直接终止。
        //if(root->val == q->val || root->val == p->val) return root;

        //左
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        //右
        TreeNode* right = lowestCommonAncestor(root->right,p,q);
        //中节点
        if(root->val == p->val || root->val == q->val){
            return root;
        }else{
            if(!left && !right) return nullptr;//说明该子树没有p也没有q
            else if(!left && right) return right;//一定要返回right。而不是root
            else if(!right && left) return left;//一定要返回left。而不是root。
            else return root;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

理解提示给节点值不重复、p和q不相等、p 和 q 均存在于给定的二叉树中

• 这个提示有用。值不相等，说明p是唯一的节点，没有p1,p2,p3……，return的一定是节点p；q同理。
• p和q不相等，且都在二叉树中，说明：
  • 情况一：p和q非包含关系。一左一右，说明left和right一个遇到p，一个遇到q。
  • 情况二：p和q包含关系。说明left或right先遇到其中之一。

---

三、【235. 二叉搜索树的最近公共祖先】题目阅读

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: 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 
解释: 节点 2 和节点 8 的最近公共祖先是 6。
1
2
3

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
1
2
3

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
1
2

---

四、【235. 二叉搜索树的最近公共祖先】题目解答

4.1 尝试解答

4.1.1思路【个人】

如果当作普通二叉树，那么上一道题肯定能解决。那么此处就要利用二叉搜索树的性质。

1. 二叉搜索树最大的特点：左子树 < 中间节点 < 右子树，数值能有序整理。这可以给搜索指明方向，就不用搜索整个树。
2. 节点p和节点q，假设p->val < q->val，始终坚持这个原则，如果不是，就要换数据。
3. 大小关系：

• 如果cur->val > q->val，说明应该遍历左子树，右子树不用遍历，得到左子树的返回之后，直接return left。
• 如果cur->val < p->val ，说明应该遍历右子树，左子树不用遍历，得到右子树的返回之后，直接return right。
• 如果p->val < cur->val < q->val，当前节点的值在中间，说明当前节点就是公共祖先。
• 可以画图辅助理解。如下：
  

4. 递归函数终止条件：上面已经说了两点终止条件。自然再加上cur为空的情况。
5. 递归函数返回值：返回节点类型。

4.1.2代码实现【递归】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    void swap(TreeNode*& p, TreeNode*& q){
        if(p->val > q->val){//设定q的值大于p的值。
            TreeNode* temp = p;
            p = q;
            q = temp;
        }
        return;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //先保证p的值小于q的值
        swap(p,q);
        //终止条件1：空节点返回空
        if(!root) return nullptr;
        //终止条件2：中间节点的值在p和q中间,或自身祖先。
        if( (p->val < root->val && root->val < q->val) || root->val == p->val || root->val == q->val) 
            return root;

        if(root->val > q->val){
            TreeNode* left = lowestCommonAncestor(root->left,p,q);//进到左子树
            return left;//此处会直接返回。没有遍历整个树。
        }else if(root->val < p->val){
            TreeNode* right = lowestCommonAncestor(root->right,p,q);//进到右子树
            return right;
        }
        return nullptr;//走不到这。
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

4.2 【235. 二叉搜索树的最近公共祖先】参考学习

参考学习链接

学习内容

1. 思路大体一致，但是代码还有改进点：

• 判断条件的处理上：中间root->val比p和q的值都大，那么遍历左子树；中间root->val比p和q的值都小，那么遍历右子树。剩下就是root->val在中间，直接返回即可。
• 因此：不需要swap(p,q) 来始终保持q的值比p大；但是第一次做，这是最直观，方便分析的思路。

2. 所以：代码改进【递归法】

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //终止条件：空节点返回空
        if(!root) return nullptr;

        if(root->val > q->val && root->val > p->val){
            TreeNode* left = lowestCommonAncestor(root->left,p,q);//进到左子树
            //没有加left为空的判断，因为题目说p和q存在。严格来说加上更通用。
            if(left) return left;//此处会直接返回。没有遍历整个树。
        }else if(root->val < p->val && root-=>val < q->val){
            TreeNode* right = lowestCommonAncestor(root->right,p,q);//进到右子树
            if(right) return right;
        }
        //中
        return root;//剩余情况。
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3. 迭代法：思路肯定一样。尝试实现下：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        queue<TreeNode*> que;
        if(!root) return nullptr;
        que.push(root);
        while(!que.empty()){
            TreeNode* cur = que.front();que.pop();
            if(cur->val > p->val && cur->val > q->val && cur->left){
                que.push(cur->left);
            }else if(cur->val < p->val && cur->val < q->val && cur->right){
                que.push(cur->right);
            }else return cur;
        }
        return nullptr;//能找到在上一行会直接return，不会走到这一行。
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

对比参考代码：上面还是有点复杂——用了队列，不过这是迭代模版，肯定能实现。
参考给出：直接用root指针交接下一棒。

---

总结

（欢迎指正，转载标明出处）