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

最近公共祖先I

最近公共祖先II

最近公共祖先III

最近公共祖先IV

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

1.对应letecode链接：
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

2.题目描述：

3.解题思路：

1.首先我们先判断根节点如果当前节点等于p或者q中的一个那么根节点就是p和q的最近公共祖先。

2.如果当前节点的值比p和q都要小那么就去左树上去找。

3.如果当前节点的值比p和q都要大那么就去右树上找

4.如果不是都大或者是都小的话说明当前节点就是p和q的最近公共祖先。

4.对应代码：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
               TreeNode*cur=root;
               while(cur)
               {
                   if(cur->val<p->val&&cur->val<q->val){
                       cur=cur->right;
                   }
                   else if(cur->val>p->val&&cur->val>q->val){
                       cur=cur->left;
                   }
                   else//说明cur是p和q的最近公共祖先
                   {
                      return cur;
                   }
               }
               return NULL;
    }
};

最近公共祖先I

1.对应letecode链接：
236. 二叉树的最近公共祖先 - 力扣（LeetCode）

2.题目描述：

3.解题思路：

首先我们先来看一个例子：

在上图中7和9的最近公共祖先是2.我们很直观的就看出来了，本题最简单的方法就是两个节点从自己出发一值往上走找到第一个相交的节点就是最近公共祖先。但是问题又来了本题中二叉树的节点当中没有父亲指针。是不是上面的方法就不行了呢？我们可以定义一个哈西表生key值对应的某个节点而val都应的是它的父亲，这样不就可以实现了吗？具体请看代码。 

4.对应代码：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        unordered_map<TreeNode*,TreeNode*>parent;//key为某个节点，val为其父亲。父亲表
        queue<TreeNode*>Q;//通过层序遍历生成父亲表
        Q.push(root);
        parent[root]=nullptr;
        while(!Q.empty()){
            auto node=Q.front();
            Q.pop();
            if(node->left){
                 Q.push(node->left);
                 parent[node->left]=node;
            }
            if(node->right){
                Q.push(node->right);
                parent[node->right]=node;
            }

        }
      //  父亲表生成完毕
        set<TreeNode*>path;
        while(p){
            path.insert(p);
            p=parent[p];//往上走
        }
        while(!path.count(q)){
            q=parent[q];//往上走；
        }
         return q;

    }
};

方法二：递归后序遍历

1.从根节点开始找判断根节点是否是p和q之中的一个如果是说明最近公共祖先就是当前的根节点root.

2.如果根节点没有找到则递归去左树和右树上去找。

3.我们使用leftRet和rightRet来接收来自左子树和右子树的结果，如果leftRet和rightRet都不为空说明左边和右边各一个那么此时根节点就是最近公共祖先。否则肯定是两个节点一边一个。此时我们只需要将不为空的那个返回即可。

4.对应代码：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
                        if(!root||root==p||root==q){
                            return root;
                        }
                      TreeNode* pqInLeft=lowestCommonAncestor(root->left,p,q);
                      TreeNode*pqInRight=lowestCommonAncestor(root->right,p,q);
                      //左右都不为空说明左边和右边各有一个
                      if(pqInLeft&&pqInRight){
                          return root;
                      }
                      return pqInRight?pqInRight:pqInLeft;
    }
};

最近公共祖先II

1.对应letecode链接：
1644. 二叉树的最近公共祖先 II - 力扣（LeetCode）

2.题目描述

3.解题思路：

本题和上题的区别是本题p和q这两个节点有可能不在树上，就只有这一个区别。那么我们是不是只需要提前查找一个p和q这两个节点是否在树上如果不在直接返回nullptr。如果使用上题的逻辑就解决了。

4.对应代码：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!Find(root,q)||!Find(root,p)){//只要p和q有一个没有在树上就说明没有最近公共祖先
            return nullptr;
        }
        return _lowestCommonAncestor( root, p, q);
    }
      TreeNode* _lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){
              if(!root||root==p||root==q){
                  return root;
              }
              auto leftRet=_lowestCommonAncestor(root->left, p, q);
              auto rightRet=_lowestCommonAncestor(root->right, p, q);
              if(leftRet&&rightRet){
                  return root;
              }
              return leftRet?leftRet:rightRet;
      }
      bool Find(TreeNode*root,TreeNode*target){
          if(root==nullptr){
              return false;
          }
          if(root->val==target->val){//找到了
              return true;
          }
        bool leftRet=Find(root->left, target);
        //左树找到了
        if(leftRet){
            return true;
        }
        bool rightRet=Find(root->right,target);
        //右树找到了
        if(rightRet){
            return true;
        }

        //左右都没找到
        return false;
      }

};

方法二：不检查节点是否存在

如果某个点x是p和q的祖先结点，情况1是x的左子树含有p和q或者右子树含有p和q，第二种情况是x本身就是p或q之一，而自己的左右子树中含有另外一个需要的值
dfs的过程的返回值的含义是以root为头结点的树中是否含有p或者q。dfs的是不断越来越深的遍历，ans更新的一定是祖先结点，随着深度加深最后更新的ans一定是最近公共祖先。

对应代码：

class Solution {
public:
TreeNode*ans=nullptr;
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        process(root, p, q);
        return ans;
    }
    bool process(TreeNode*root,TreeNode*p,TreeNode*q){
        if(root==nullptr){
            return false;
        }
        bool leftRet=process(root->left,p,q);
        bool rightRet=process(root->right,p,q);
        if(leftRet&&rightRet){
            ans=root;
        }
        //根节点的值有一个和root相等并且左子树和右子树要发现p和q其中的一个
        if((root->val==p->val||root->val==q->val)&&(leftRet||rightRet)){
            ans=root;
        }
        return p->val==root->val||q->val==root->val||leftRet||rightRet;
    }
};

最近公共祖先III

1.对应letecode链接
1650. 二叉树的最近公共祖先 III - 力扣（LeetCode）

2.题目描述：

3.解题思路：

本题和第二题介绍的第一种方法非常的相似我们可以使用它来解决这道题（在这里就不重复了），我们让两个节点都往上走找到第一个相交的节点。这不就是链表相交问题吗？

不太清楚的老铁可以看一下我的博客。

4.对应代码

class Solution {
public:
    Node* lowestCommonAncestor(Node* p, Node * q) {
         Node*curP=p;
         Node*curQ=q;
         while(curP!=curQ){
             curP=curP?curP->parent:q;
             curQ=curQ?curQ->parent:p;
         }
         return curP;
    }
};

最近公共祖先IV

1.对应letecoede链接：
1676. 二叉树的最近公共祖先 IV - 力扣（LeetCode）

2.题目描述：

3.解题思路：

这题和上面这些题非常类似思路基本相同。依题意，nodes中的所有节点均存在于二叉树中
因而，{nodes中所有节点的最近公共祖先}，可以弱化为{当前子树上的隶属于nodes中的所有节点的最近公共祖先}，这样就无需考虑是否包含了nodes中的全部节点了。
1）若子树的root是nodes中的节点，则其必为该子树上隶属于nodes的所有节点的最近公共祖先。因为其本身就是该子树的根了(包含了当前子树的整个范围不能再往上了)，且其自身隶属于nodes因而也不能再往下了(再往下就漏掉了root本身)；
2）若root的左右子树上均存在nodes中的节点，则root就是最近公共祖先；
3）若nodes中的节点都存在于某个子树，则返回该子树上所有隶属于nodes中的节点的公共祖先即可；
4）若整个root子树上不存在nodes中的节点，则该子树上隶属于nodes中的节点的公共祖先就是nullptr。

4.对应代码：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, vector<TreeNode*> &nodes) {
                if(root==nullptr){
                    return nullptr;
                }
                for(auto x:nodes)
                {
                    if(x==root){
                        return root;
                    }
                }
                TreeNode*leftRet=lowestCommonAncestor(root->left, nodes);
                TreeNode*righRet=lowestCommonAncestor(root->right, nodes);
                if(leftRet&&righRet){
                    return root;
                }
                return leftRet?leftRet:righRet;
    }
};