代码随想录 | Day24 | 二叉树：二叉树的公共祖先（有个自己的想法）二叉搜索树的公共祖先
代码随想录 | Day24 | 二叉树：二叉树的公共祖先（有个自己的想法）&&二叉搜索树的公共祖先
主要学习内容：
1.一般需要向上返回下层结点的内容信息或者判断结果的话都是后序遍历
2.二叉搜索树的性质：左右子树和根结点的大小关系
236.二叉树的最近公共祖先
236. 二叉树的最近公共祖先 - 力扣（LeetCode）
解法：后序遍历
自己的想法思路：
首先，在本题中，我们要找的是结点的公共祖先，但是祖先结点不会知道我下面到底有没有咱们要找的p，q结点，不知道自己是不是所谓的祖先。所以我们需要判断完有没有p，q结点之后，在返回结果给上层结点，让它知道自己是祖先结点，因此采用的是后序遍历。
通过分析题意，我们可以知道p，q和它俩的祖先结点的分布大概有两种情况
1.p，q分别在祖先结点的左右子树
2.祖先结点就是p或q本身
而不会有第三种情况，因为祖先结点可以是p或q本身。假设祖先结点不是p或q本身，但是p和q都在祖先结点的左子树或者右子树，那这样遍历的话，一定会先遇到p或者q，然后剩下的一个就在它的子树，即先遇到的p或q就是祖先结点。
接下来就是分情况写出对应的代码
首先先看一下
1.函数参数和返回值
TreeNode *res=nullptr;//记录答案
bool flag=true;//控制res只被修改一次，即只记录最近公共祖先
bool tra(TreeNode* t, TreeNode* p, TreeNode* q)//返回值是bool，来判断子树或者本层结点是不是q或p
2.终止条件
if(t==nullptr)
return false;
if(t==p||t==q)
return true;
空说明没有找到p或q，向上层返回的结果就是false代表没找到。
3.本层代码逻辑
第一种情况：p，q分别在祖先结点的左右子树
那么左右子树的遍历结果一定都会是true，flag作为标志只需要改一次就是最近的祖先结点，答案记录后将标志修改。
bool l=tra(t->left,p,q);//在左子树找p或q
bool r=tra(t->right,p,q);//在右子树找p或q
if(l&&r==true && flag==true)
{
res=t;
flag=false;
}
第二种情况
首先，如果p或q是祖先结点的情况下，我们在遍历过程中一定会知道有个结点是等于p或者q的，那我们只需要判断剩下的一个结点有没有在本结点左右子树被找到过，如果被找到过，那说明当前结点就是我们要找到答案，更新res和flag即可。如果没有的话，那当前结点就是祖先结点子树中的结点，照常往上返回我们找到了p或q就行
比如，我们遍历到5的时候只需要看左右子树有没有找到4，发现右子树找到了4，那说明5本身就是祖先。进入if却在子树中没有，那说明我们找到的是4，在5的子树中，往上返回true表示我们找到了4就行。
bool l=tra(t->left,p,q);
bool r=tra(t->right,p,q);
if(t==p||t==q && flag==true)
{
if(l || r)
{
res=t;
flag=false;
}
else
return true;
}
其中return true其实就是终止条件的第二条，所以就把终止条件第二个if给省略掉。
本层逻辑的完整代码：
bool l=tra(t->left,p,q);
bool r=tra(t->right,p,q);
if(t==p||t==q && flag==true)
{
if(l || r)
{
res=t;
flag=false;
}
else
return true;
}
else if(l&&r==true && flag==true)
{
res=t;
flag=false;
}
return l || r;
最后注意的细节是我们返回的是 l||r，因为不管怎么样，只要左右子树中找到了随便一个，我们都会往上返回我们找到了
完整代码：
class Solution {
public:
TreeNode *res=nullptr;
bool flag=true;
bool tra(TreeNode* t, TreeNode* p, TreeNode* q)
{
if(t==nullptr)
return false;
bool l=tra(t->left,p,q);
bool r=tra(t->right,p,q);
if(t==p||t==q && flag==true)
{
if(l || r)
{
res=t;
flag=false;
}
else
return true;
}
else if(l&&r==true && flag==true)
{
res=t;
flag=false;
}
return l || r;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
bool r=tra(root,p,q);
return res;
}
};
代码随想录的解法
完整代码：
class Solution {
public:
TreeNode* tra(TreeNode* t, TreeNode* p, TreeNode* q)
{
if(t==nullptr)
return t;
if(t==p||t==q)
return t;
TreeNode *l=tra(t->left,p,q);
TreeNode *r=tra(t->right,p,q);
if(l!=nullptr&&r!=nullptr) return t;
else if(l!=nullptr&&r==nullptr) return l;
else if(l==nullptr&&r!=nullptr) return r;
else
return nullptr;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return tra(root,p,q);
}
};
个人感觉这个不太好想，也不太好理解，因为把两种情用一种情况代码给表示了，包含了第二种情况，所以比较难想。
首先我和代码随想录的区别是，我是用bool来表示找到没找到，它用返回值是否非空来表示。它只要没找到那一定返回的是nullptr，找到了那就是不为空的，把返回值类型和答案类型统一，不用有额外的res记录答案。
第一种情况代码是
即左右子树中分别找到了p或q，那么本层结点就是祖先结点
if(l!=nullptr&&r!=nullptr) return t;
第一个难理解的点是：通过一直返回一样的结点来保证返回的是最近的祖先结点。
假设p，q是7,4，那么在5这一层返回给3的是r，而r是5的右子树递归的结果，5的右子树递归的返回值就是2，即我们要的答案。这是第一个难理解的点。
第二个难理解的点是两种情况合并到一起了
你会发现如果是第二种情况，当我们找到祖先结点的时候，我们压根不往下找，直接返回的就是祖先结点，虽然我们不知道这个是祖先结点。但我们知道，如果q或p本身是祖先结点，那么另外一个肯定在祖先结点的子树，所以也没有必要往下找。
比如上图的5,4，找到5以后，直接就在终止条件部分就给往上返回走了，就不去管4。
到这里大家也就明白了，只有第一种情况需要去找到4，第二种情况找到5就没必要找4。
这但比较难想
if(t==p||t==q)
return t;
if(l!=nullptr&&r!=nullptr) return t;
else if(l!=nullptr&&r==nullptr) return l;
else if(l==nullptr&&r!=nullptr) return r;
else
return nullptr;
难点：
1.递归的理解
2.两种情况如何合并到了一起
235.二叉搜索树的最近公共祖先
235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）
解法：直接二分查找
思路：
这个题不需要太过复杂的思想，情况也不用分的太清楚
就是在区间[p,q]或[q,p]的就是答案，至于最近的公共祖先会随着遍历更新到最进的祖先。
t比p,q都大那就是在左子树，小的话就是右子树
class Solution {
public:
TreeNode *res=nullptr;
void tra(TreeNode* t, TreeNode* p, TreeNode* q)
{
if(t==nullptr)
return;
//[p,q]
if(t->val>=p->val&&t->val<=q->val)
{
res=t;
return ;
}
//[q,p]
else if(t->val<=p->val&&t->val>=q->val)
{
res=t;
return ;
}
//左子树
else if(t->val>p->val&&t->val>q->val)
tra(t->left,p,q);
//右子树
else if(t->val<q->val&&t->val<p->val)
tra(t->right,p,q);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
tra(root,p,q);
return res;
}
};
代码随想录：
也是分了三种情况，左边找到了就返回左边left，右边找到了就返回返回right，都没找到说明就是本层结点，返回本身。
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);
}
};