Have you really learned the common ancestor problem recently?

Catalog

Search for the nearest common ancestor of a binary tree

Recent public ancestor I

Recent public ancestor II

Recent public ancestor III

Recent public ancestor IV

---

Search for the nearest common ancestor of a binary tree

1. Corresponding letecode link ：

The finger of the sword Offer 68 - I. The nearest common ancestor of a binary search tree - Power button （LeetCode）

2. Title Description ：

 

3. Their thinking ：

1. First, we judge the root node if the current node is equal to p perhaps q One of the root nodes in is p and q The latest public ancestor of .

2. If the value of the current node is greater than p and q If you want to be small, go to the tree on the left .

3. If the value of the current node is greater than p and q If you want to be big, go to the right tree

4. If they are not both large or small, the current node is p and q The latest public ancestor of .

4. The corresponding code ：

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// explain cur yes p and q The latest public ancestor of 
                   {
                      return cur;
                   }
               }
               return NULL;
    }
};

Recent public ancestor I

1. Corresponding letecode link ：

236. The nearest common ancestor of a binary tree - Power button （LeetCode）

2. Title Description ：

3. Their thinking ：

Let's start with an example ：

In the diagram above 7 and 9 The most recent public ancestor of 2. We can see it intuitively , The simplest way to solve this problem is to start from two nodes and go up by one value to find that the first intersecting node is the nearest common ancestor . But the problem comes again. In this problem, there is no parent pointer in the nodes of the binary tree . Is the above method not working ？ We can define a Hassy supergene key Value corresponds to a node and val Should be its father , This can be achieved ？ Please refer to the code for details. . 

4. The corresponding code ：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        unordered_map<TreeNode*,TreeNode*>parent;//key For a node ,val For his father . Father's Watch 
        queue<TreeNode*>Q;// Generate parent table through sequence traversal 
        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;
            }

        }
      //   The parent table is generated 
        set<TreeNode*>path;
        while(p){
            path.insert(p);
            p=parent[p];// Go up 
        }
        while(!path.count(q)){
            q=parent[q];// Go up ;
        }
         return q;

    }
};

Method 2 ： Recursive postorder traversal

1. Start from the root node to determine whether the root node is p and q If one of these indicates that the nearest common ancestor is the current root node root.

2. If the root node is not found, return to the left tree and the right tree .

3. We use leftRet and rightRet To receive results from the left and right subtrees , If leftRet and rightRet If neither is empty, it means that there is one on the left and one on the right, then the root node is the nearest common ancestor . Otherwise, there must be two nodes, one on each side . At this point, we just need to return the non empty one .

4. The corresponding code ：

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);
                      // Left and right are not empty, which means there is one on the left and one on the right 
                      if(pqInLeft&&pqInRight){
                          return root;
                      }
                      return pqInRight?pqInRight:pqInLeft;
    }
};

Recent public ancestor II

1. Corresponding letecode link ：

1644. The nearest common ancestor of a binary tree II - Power button （LeetCode）

2. Title Description

 

 3. Their thinking ：

The difference between this question and the previous question is that this question p and q These two nodes may not be in the tree , There is only one difference . So we just need to find one in advance p and q Whether these two nodes are in the tree. If not, they will return directly nullptr. If we use the logic of the above question, we will solve the problem .

 4. The corresponding code ：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!Find(root,q)||!Find(root,p)){// as long as p and q If one is not in the tree, it means that there is no nearest common ancestor 
            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){// eureka 
              return true;
          }
        bool leftRet=Find(root->left, target);
        // Left tree found 
        if(leftRet){
            return true;
        }
        bool rightRet=Find(root->right,target);
        // The right tree found 
        if(rightRet){
            return true;
        }

        // I can't find it left or right 
        return false;
      }

};

Method 2 ： Do not check whether the node exists

If a point x yes p and q The ancestral node of , situation 1 yes x The left subtree of contains p and q Or right subtree contains p and q, The second situation is x Itself is p or q One of , The left and right subtrees contain another required value
dfs The meaning of the return value of the procedure of is in the form of root Whether the tree with the header node contains p perhaps q.dfs What we need is to go deeper and deeper ,ans The updated node must be the ancestor node , As the depth deepens, the last updated ans Must be the nearest common ancestor .

The corresponding code ：

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;
        }
        // The value of the root node has an and root Equal and left subtree and right subtree to be found p and q One of them 
        if((root->val==p->val||root->val==q->val)&&(leftRet||rightRet)){
            ans=root;
        }
        return p->val==root->val||q->val==root->val||leftRet||rightRet;
    }
};

Recent public ancestor III

1. Corresponding letecode link

1650. The nearest common ancestor of a binary tree III - Power button （LeetCode）

2. Title Description ：

 3. Their thinking ：

This question is very similar to the first method introduced in question 2. We can use it to solve this problem （ I won't repeat it here ）, Let's make both nodes go up to find the first intersecting node . This is the problem of linked list intersection ？

Lao tie, who is not very clear, can take a look at my blog .

4. The corresponding code

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;
    }
};

Recent public ancestor IV

1. Corresponding letecoede link ：

1676. The nearest common ancestor of a binary tree IV - Power button （LeetCode）

2. Title Description ：

  3. Their thinking ：

This question is very similar to the above questions, and the train of thought is basically the same . According to the question ,nodes All nodes in the exist in the binary tree
thus ,{nodes The nearest common ancestor of all nodes in }, Can be weakened to { The current subtree belongs to nodes The nearest common ancestor of all nodes in }, In this way, there is no need to consider whether it includes nodes All nodes in .
1） If subtree root yes nodes The nodes in the , Then it must belong to nodes The nearest common ancestor of all nodes of . Because it is the root of the subtree itself ( The entire range that contains the current subtree can no longer go up ), And it belongs to nodes So we can't go any further ( If you go down, you'll miss it root In itself );
2） if root On both the left and right subtrees of nodes The nodes in the , be root The most recent public ancestor ;
3） if nodes All the nodes in the exist in a subtree , Then all the members of the subtree are returned nodes The common ancestor of the node in ;
4） If the whole root The subtree does not exist nodes The nodes in the , Then the subtree belongs to nodes The common ancestor of a node in is nullptr.

4. The corresponding code ：

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;
    }
};