前言
公共祖先解决。二叉树和二叉搜索树条件下的最近公共祖先。
二叉树篇继续。
一、【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 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
提示：
树中节点数目在范围 [2, 10^5] 内。
-10^9 <= Node.val <= 10^9
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。
二、【236. 二叉树的最近公共祖先】题目解答
弯路（第一次做题时，可能的想法）
- 二叉树习惯用递归法解决问题，那么需要确定遍历顺序和重复执行的递归逻辑。
- 本题是二叉树，需要求最近公共祖先，那么父节点应该是最后遍历。所以尝试遍历顺序：后序——左右中。
- 如何找到统一执行的规律呢？回到中间节点需要处理什么逻辑？
- 受前几节二叉搜索树中序遍历整合到数组中，那么此处遍历结果数组得到之后，看p,q哪个在前，选择在前面的p或者q？可是无法区分自己是祖先的情况。（不正确）
正确思路获取
- 确定后序遍历，因为需要从节点p,q向上退出父节点，所以中间节点最后处理。（左右中）
- 返回中间节点什么信息？判断左子树中是否存在p或q，判断右子树中是否存在p或q：
-
如果左子树有p，右子树有q；左子树有q，右子树有p。此时返回中间节点（最近公共祖先）。
-
如果一边子树为空，另一边子树有p或q之一。此时返回left或者right，即子树返回的节点。注意：这里不能返回中间节点。会把最近公共祖先丢掉。
-
如果两边子树都为空，说明该中间节点的左右子树不包含p和q。向上返回空。
- 所以递归函数返回值：TreeNode* 类型；
- 递归函数终止条件：如果cur是空，return空。如果cur->val是p或q，return cur。
- 两个终止条件：第一个空判断可以容易想到。
- 如果第二个终止条件没有想到：影响吗？可以拯救：在中间逻辑先判断该节点是否为p或q，如果是，那么return cur；如果不是，走第2.点的逻辑。
- 所以第二个终止条件放到中间节点之前，更简单。
- 总结：左右中：先看左右子树能向中间节点返回什么信息——空节点说明不包含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;
}
};
补充说明【细节】
补充思路中没提及的情况2：自身是祖先——以上代码在哪一处包含
- p和q不是包含关系，情况1：肯定是某个中间节点的两边子树；
- 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;
}
}
};
理解提示给节点值不重复、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。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
四、【235. 二叉搜索树的最近公共祖先】题目解答
4.1 尝试解答
4.1.1思路【个人】
如果当作普通二叉树，那么上一道题肯定能解决。那么此处就要利用二叉搜索树的性质。
- 二叉搜索树最大的特点：左子树 < 中间节点 < 右子树，数值能有序整理。这可以给搜索指明方向，就不用搜索整个树。
- 节点p和节点q，假设p->val < q->val，始终坚持这个原则，如果不是，就要换数据。
- 大小关系：
- 如果cur->val > q->val，说明应该遍历左子树，右子树不用遍历，得到左子树的返回之后，直接return left。
- 如果cur->val < p->val ，说明应该遍历右子树，左子树不用遍历，得到右子树的返回之后，直接return right。
- 如果p->val < cur->val < q->val，当前节点的值在中间，说明当前节点就是公共祖先。
- 可以画图辅助理解。如下：
- 递归函数终止条件：上面已经说了两点终止条件。自然再加上cur为空的情况。
- 递归函数返回值：返回节点类型。
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;//走不到这。
}
};
4.2 【235. 二叉搜索树的最近公共祖先】参考学习
学习内容
- 思路大体一致，但是代码还有改进点：
- 判断条件的处理上：中间root->val比p和q的值都大，那么遍历左子树；中间root->val比p和q的值都小，那么遍历右子树。剩下就是root->val在中间，直接返回即可。
- 因此：不需要swap(p,q) 来始终保持q的值比p大；但是第一次做，这是最直观，方便分析的思路。
- 所以：代码改进【递归法】
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;//剩余情况。
}
};
- 迭代法：思路肯定一样。尝试实现下：
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，不会走到这一行。
}
};
对比参考代码：上面还是有点复杂——用了队列，不过这是迭代模版，肯定能实现。
参考给出：直接用root指针交接下一棒。
总结
（欢迎指正，转载标明出处）