Leetcode -- the nearest common ancestor of 236 binary tree

Train of thought

subject

If the interviewer asks the nearest common ancestor of a binary tree , We can ask the interviewer , Is this binary tree a search tree , If it's a search tree
Here's the picture ：

The characteristic of search tree is ： The left child is younger than his father , The right child is older than his father . Then we can analyze ：2,3 The most recent public ancestor of 3,0,4 The most recent public ancestor of 3, 6 and 9 My nearest ancestor was 7. Then it can be concluded that ： A child node is smaller than the root , A child node is larger than the root , This root is the nearest common ancestor , If 2 There are... In nodes 1 The first is the root node, so this node is the nearest common ancestor

Ordinary binary tree

From the above ideas ：
1.2 All nodes are in the left subtree , Recurse to the left tree to find
2.2 All nodes are in the right subtree , Recurse to the right tree to find
3. If 1 One on the left and one on the right , The root node is the nearest common ancestor , If 2 There are... In nodes 1 The first is the root node, so this node is the nearest common ancestor
At this time, you need to write a recursive search node , here Node to be used To compare , Out-of-service val To compare , If val There will be miscarriage of justice . Also pay attention to naming , Bad naming is easy to confuse others , Or the interviewer doesn't give a score .

The code is as follows ：

class Solution {
    
public:
 bool find(TreeNode* root,TreeNode* x)
 {
    
     //root Empty to return directly to 
    if(root == nullptr)
    return false;
    if(root == x)
    return true;
   // If you are not in the left subtree, go to the right subtree , Use or here 
    return find(root->left,x) || find(root->right,x);

 }
 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
 // If 2 Among them 1 The first is the root. At this time, the root is the nearest public ancestor 
        if(p == root || q == root)
        {
    
            return root;
        }
        // Definition 4 individual bool value , Namely p In the left subtree and the right subtree 
        //q and p Just the same 
        bool pInLeft,pInRght,qInLeft,qInRght;
        //p On the left, it won't be in the right subtree 
        //q It's the same operation 
        pInLeft = find(root->left,p);
        pInRght = !pInLeft;
        qInLeft = find(root->left,q);
        qInRght = !qInLeft;
       // If 2 All of them are in the left subtree , Continue to recurse to the left subtree to find 
        if(pInLeft && qInLeft)
        {
    
            return lowestCommonAncestor(root->left,p,q);
        }
         // If 2 All of them are in the right subtree , Continue to recurse to the right subtree to find 
        else if(pInRght && qInRght)
        {
    
            return lowestCommonAncestor(root->right,p,q);
        }
        // One on the left and one on the right , The root is the nearest common ancestor 
        else
        {
    
            return root;
        }
    }
};

analysis ： If the binary tree is a full binary tree or a complete binary tree , The time complexity at this time is O(nlogn), The extreme case is a single tree , The time complexity at this time is O(N^2). At this time, the time complexity required by the interviewer is O(N), Then how to solve it ？

Train of thought two

look for 2 The path of nodes , Use the stack to save the path , To find the intersection node .

The code is as follows ：

class Solution {
    
public:
   bool findPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
   {
    
       if(root == nullptr)
       return false;
       // If the root node is not empty, enter the stack 
       path.push(root);

       if(root == x)
       return true;
       // Found return true
       if (findPath(root->left,x,path))
       {
    
           return true;
       }
        if(findPath(root->right,x,path))
       {
    
           return true;
       }
       // It's not the right path to go here ,pop take false Back to the next level 
       path.pop();
       return false;
   }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
        // Definition 2 Stack save path 
      stack<TreeNode*> pPath;
      stack<TreeNode*> qPath;
      // find p and q The path of 
      findPath(root,p,pPath);
      findPath(root,q,qPath);
      // use 2 Pointer to compare the length 
      stack<TreeNode*>*shortPath = &pPath;
      stack<TreeNode*>*longtPath = &qPath;
      // I don't know which path is long , At this time, it defaults to 1 Long , In comparison , If the default long and short are exchanged 
      if(pPath.size() > qPath.size())
      {
    
          swap(shortPath,longtPath);
      }
      // Let the long walk the gap first , Walking at the same time 
      while(shortPath->size() < longtPath->size())
      {
    
         longtPath->pop();
      }
      // Walk at the same time and compare whether the elements at the top of the stack are equal , The first 1 Even the nearest common ancestor 
      while(shortPath->top() != longtPath->top())
      {
    
          longtPath->pop();
          shortPath->pop();
      }
      return shortPath->top();
        }
};

We just passed .
analysis ：

It can be seen that thinking two is much faster than one , Time complexity analysis ：2 The path to stack is O(N),2 Stack comparison is also O(N), That is to say O(4N), The final time complexity is O(N).