Code Caprice record day22

A, binary search tree search

   Topic link force buckle 700

Let’s first introduce the binary search tree. The binary search tree is regular. The left child of the root node is always smaller than the root node, and the right child of the root node is always larger than the root node (except when the right child is null), so binary search It is easier to traverse the tree.

How to do the question: Think clearly about the three conditions of recursion before doing the question; 1: Determine the parameters and return value of the recursive function 2: Determine the termination condition 3: Determine the logic of the single-level recursion The following three questions use this step

It is similar to the traversal of ordinary binary trees. This problem also adopts a recursive method. If root.val>val, it means that the target value is on the left, so the operation of root.left is performed; root.val<val, the target value is indicated. On the right side of root, the operation of root.right is performed.

code show as below:

class Solution {
    // Recursion, using the characteristics of binary search tree, optimization
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        if (val < root.val) {
            return searchBST(root.left, val);
        } else {
            return searchBST(root.right, val);
        }
    }
}

2. The nearest common ancestor of a binary search tree

Topic link force buckle 235

Problem solving idea: This is all solved by recursive method. When root.val is greater than p and q at the same time, root.left is executed, and when root.val is smaller than p and q at the same time, root.right is executed. , and eventually the nearest ancestor of p and q can be found.

class Solution {
    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;
    }
}

Third, the insertion operation in the binary search tree

Topic link force buckle 701

 

The idea of ​​​​doing the question: Because the binary search tree is regular, the inserted node must fall on the tail node, so that the structure of the binary search tree will not be changed, and it will be better to do it. (The third picture can be ignored, Don't think about that way of writing). This question still uses the recursive method, which is similar to the method of the previous two questions. When root.val>val, execute the operation of root.left, and keep searching to the left. The right side is the opposite, so I will not write it. When the last position is reached, that is, when root==null, the target node is inserted at that position. There are also a few points that need to be paid attention to. I wrote it in the code comments for easy viewing;

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
         if(root==null){
             TreeNode node=new TreeNode(val);
             return node;//return node to the previous root.left (or right),
                          //Then let the previous root point to node
         }

         if(root.val>val){
             root.left=insertIntoBST(root.left,val);
         }
         if(root.val<val){
             root.right=insertIntoBST(root.right,val);
         }
         return root;
    }
}

Fourth, delete the node in the binary search tree

Topic link force buckle 405

How to do the question: This question also uses a recursive method, but there are several situations, you have to think about it clearly first,

1. There is no target node

2. When both left and right children are empty

3. When the left child is empty, the right child is not empty

4. When the left child is not empty, the right child is empty

5. The case where neither the left child nor the right child is empty (this is the most complicated case, and the structure of the binary search tree has to be changed) Detailed steps,

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
       if(root==null)return null;
       if(root.val==key){
           if(root.left==null&&root.right==null)return null;
           else  if(root.left!=null&&root.right==null) return root.left;
           else  if(root.left==null&&root.right!=null) return root.right;
           else if(root.left!=null&&root.right!=null){
           TreeNode cur=root.right;
           while(cur.left!=null){
               cur=cur.left;
           }
           cur.left=root.left;
           root=root.right;
             return root;
           }
         
       }
       if(root.val>key) root.left= deleteNode(root.left,key);
       if(root.val<key) root.right= deleteNode(root.right,key);
       return root;
    
    }
}