Notes on writing questions (18) -- binary tree: common ancestor problem

List of articles

Brush notes （ One ）– An array type ： Dichotomy
Brush notes （ Two ）– An array type ： Double finger needling
Brush notes （ 3、 ... and ）– An array type ： The sliding window
Brush notes （ Four ）– An array type ： simulation
Brush notes （ 5、 ... and ）– List type ： Basic topics and operations
Brush notes （ 6、 ... and ）– Hashtable ： Basic topics and ideas
Brush notes （ 7、 ... and ）– character string ： Classic title
Brush notes （ 8、 ... and ）– Double pointer ： Sum of two numbers and extension
Brush notes （ Nine ）– character string ：KMP Algorithm
Brush notes （ Ten ）– Stacks and queues ： Basic topics
Brush notes （ 11、 ... and ）– Stacks and queues ：Top-K problem
Brush notes （ Twelve ）– review ： Sorting algorithm
Brush notes （ 13、 ... and ）– Binary tree ： Traversal in front, middle and back order （ review ）
Brush notes （ fourteen ）– Binary tree ： Sequence traversal and DFS,BFS
Brush notes （ 15、 ... and ）– Binary tree ： Attribute related topics
Brush notes （ sixteen ）– Binary tree ： Modification and construction
Brush notes （ seventeen ）– Binary search tree ： About attributes

Preface

The binary tree is almost over , come on. ！！！

Bibliography

236. The nearest common ancestor of a binary tree

The title links are as follows ：

236. The nearest common ancestor of a binary tree

The screenshot of the title is as follows ：

How to do this problem ？ In fact, it should be carried out step by step

Step one

Give the root node , And target nodes , Then check whether the target node is a subtree of the root node . This is very simple, not ？

public boolean find(TreeNode root,TreeNode target){
    
        if(root == null) return false;
        if(root == target) return true;
        return find(root.left,target) || find(root.right,target);
    }

Step two

Then it must be discussed according to the situation

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        // The next step is to make a judgment 
        if(root == null) return null;
        if(root == p || root == q) return root;// if p perhaps q Any one is the root node , The ancestor must be the root node 
        // if p q The nodes are on the left , Then go to Zuozi tree to find your ancestors 
        if(find(root.left,p) && find(root.left,q)) return lowestCommonAncestor(root.left,p,q);
        // if p q The nodes are on the right , Then go to Youzi tree to find your ancestors 
        if(find(root.right,p) && find(root.right,q)) return lowestCommonAncestor(root.right,p,q);
        // If not on one side at the same time , The current node must be the ancestor 
        return root;
    }

Step three

What's the third step ？ It must be simplification , It must be possible to write like that , But it's a little long . Code first , Then explain the code

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        if(root == null || root == p || root == q) return root;// This step is the key 
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left == null && right == null) return null;
        if(left == null) return right;
        if(right == null) return left;
        return root;
    }

This code is to merge step one and step , But here …emmm, The point is ： After the sequence traversal . Same as above , Look at it in two steps

Step one ：

That's the first step , Is a recursive process , Then look for p and q node .

This is the second step , It's about judging what you're looking for .

These two steps are the decomposition of each layer of recursion , It seems a bit chaotic, isn't it ？？emmm, Stop for a second , In the future, if I can organize my own language, I will continue .

235. The nearest common ancestor of a binary search tree

Topic link ：

235. The nearest common ancestor of a binary search tree

Title screenshot ：

In fact, it can be treated as an ordinary tree , But since the binary search tree is mentioned here , It's the same as the last question , Even the code doesn't have to change .

But what? , Since the binary search tree is mentioned here , Then the current time complexity can be optimized by the properties of binary search tree .

public class  The common ancestor of binary search tree  {
    
    // The common ancestor of a binary tree is the postorder traversal , I can also follow up here ？ My first thought is the preorder traversal 
    // Preorder traversal is still a little problematic ,return root repeated 
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        if(root.val > p.val && root.val > q.val){
    
            return lowestCommonAncestor(root.left,p,q);
        }
        if(root.val < p.val && root.val < q.val){
    
            return lowestCommonAncestor(root.right,p,q);
        }
        return root;
    }
}