[code Capriccio] column of binary tree and binary search tree (java version with comments)

preface

For the supplement of the following code, see the following link:
Binary tree theory and code in code Capriccio

This paper mainly studies according to the learning route of the link, reading its ideas and self cognition, and adding code comments
Convenient for self-study, interested students can also collect and pay attention

There is no code recollection in the binary tree column. It is mainly the code sequence and some ideas or diagrams cited

1. Conventional algorithm

It is very common to use pre order or post order in iteration, especially in recursion

1.1 recursive traversal

Preorder traversal · recursion · LC144_ Preorder traversal of binary tree

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }

    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preorder(root.left, result);
        preorder(root.right, result);
    }
}

Medium order traversal · recursion · LC94_ Middle order traversal of binary tree

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);             // 
        inorder(root.right, list);
    }
}

Postorder traversal · recursion · LC145_ Binary Tree Postorder Traversal

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

    void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);             // 
    }
}

1.2 iterative traversal

The iterative traversal here does not use the code of code random record. If you are interested, you can search Baidu, and its unified iterative traversal can also be used

//Preorder traversal
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }

        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        while (node != null||!stack.isEmpty() ) {
            while (node != null) {
                list.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return list;
    }
}

Middle order traversal

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> stk = new LinkedList<>();

        while (root != null || !stk.isEmpty()) {
            while (root != null) {
               
                stk.push(root);
                root = root.left;

            }

            root = stk.pop();
            list.add(root.val);
            root = root.right;
        }
        return list;
    }
}

Postorder traversal

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        if(root==null)return list;

        LinkedList<TreeNode> stk=new LinkedList<>();
        //Create a null pointer, mainly to remember the root node and go back
        TreeNode prev=null;
        while(root!=null||!stk.isEmpty()){
            while(root!=null){
                stk.push(root);
                root=root.left;
            }
            //Traverse the right node after leaving the stack
            root=stk.pop();
           //If there is no data on the right, add the node to the list. And set its root to empty, mainly to get it out of the stack and back up a grid
            if(root.right==null||root.right==prev){
                list.add(root.val);
                //The grid that goes back up is marked prev
                prev=root;
                root=null;        
            }else{
                 //If there is data on the right, continue to enter the stack
                stk.push(root);
                root=root.right;
            }
        }
        return list;

    }
}

1.3 level traversal

Start level traversal from top to bottom:

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list=new ArrayList<List<Integer>>();
        if(root==null) return list;

        Queue <TreeNode> que=new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            List<Integer>sonlist=new LinkedList<>();
            
            int n=que.size();
            for(int i=0;i<n;i++){                
                TreeNode node= que.poll();
                sonlist.add(node.val);
                if(node.left!=null)que.offer(node.left);
                if(node.right!=null)que.offer(node.right);
            }
            
            list.add(sonlist);           

        }
        return list;

    }
}

Start the level traversal from bottom to top: modify the final code format to list add(0,sonlist);

Output right view of binary tree: output the last node in each size
leetcode: 199. Right view of binary tree

Output the average number of traversals of each level
leetcode: 637. Layer average of binary tree

The hierarchical traversal of N-ary tree. Pay attention to the differences:
leetcode: 429. Sequence traversal of n-ary tree

leetcode: 515. Find the maximum value in each tree row

The following returned node is not a list. To distinguish it, the complete code and comments are released here
leetcode: 116. Populate the next right node pointer for each node

class Solution {
    public Node connect(Node root) {
        //No, it's the wrong type
        //List<Node> list=new ArrayList<>();

        if(root==null)return root;
        LinkedList<Node> que=new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            int n=que.size();
            
            for(int i=0;i<n;i++){
                Node node =que.poll();
                
                //Don't use this
                //list.add(node);
                //if(i==n-1)list.add(node.next);
                
                //For the connected nodes, the next step of the hierarchy traversal is the next peek in the queue. Just string them together
                if(i<n-1)node.next=que.peek();
                if(node.left!=null)que.offer(node.left);
                if(node.right!=null)que.offer(node.right);
            }
        }

        //The returned node is node, that is, the root node has changed
        return root;
        
    }
}

The above ideas can also be applied to this problem
leetcode: 117. Fill in the next right node pointer II of each node

Binary tree

226. Flip binary tree (simple)

leetcode: 226. Flip binary tree

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null)return null;
        //Record the value in a node in order to recursively point to the root
        TreeNode l=invertTree(root.left);
        TreeNode r=invertTree(root.right);
        root.left=r;
        root.right=l;
        return root;

    }
}

Or directly invert in the node:

public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }

    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;

    invertTree(root.left);
    invertTree(root.right);
    return root;
}

Even use hierarchy traversal to flip the nodes in each layer

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        LinkedList<TreeNode> que=new LinkedList<>();
        que.offer(root);
        //The left and right nodes are reversed when traversing each layer
        while(!que.isEmpty()){
            TreeNode node= que.poll();

            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;

            if(node.left!=null)que.offer(node.left);
            if(node.right!=null)que.offer(node.right);

        }
        return root;
    }
}

Incorrect writing:

101. Symmetric binary tree (simple)

leetcode: 101. Symmetric binary tree

Recursive approach:

class Solution {
    public boolean isSymmetric(TreeNode root) {

        return ss(root,root);

    }
    public boolean ss(TreeNode L1,TreeNode L2){
        if(L1==null&&L2==null) return true;
        if(L1 ==null ||L2==null) return false;
         
        //The condition of each recursion is that the values are equal, and the L1 left pointer is equal to the L2 right pointer, and the L1 right pointer is equal to the L2 left pointer
        return  L1.val==L2.val && ss(L1.left,L2.right) && ss(L1.right,L2.left);

    }
}

Breadth first traversal:

class Solution {
    public boolean isSymmetric(TreeNode root) {

        return ss(root,root);

    }
    //The returned type is boolean
    public boolean ss(TreeNode L1,TreeNode L2){
        LinkedList<TreeNode> que=new LinkedList<>();
        //After traversing the hierarchy, the root node is added again
        que.offer(L1);
        que.offer(L2);
        while(!que.isEmpty()){
            //When outputting, it is returned to u and v
            TreeNode u= que.poll();
            TreeNode v = que.poll();

            //If both are null, continue
            if(u==null&&v==null)continue;
            //If one of the three conditions is not satisfied, it returns false
            if(u==null||v==null||u.val!=v.val)return false;

            //See the order when entering the queue
            que.offer(u.left);
            que.offer(v.right);

            que.offer(u.right);
            que.offer(v.left);
        }
        return true;

    }
}

104. Maximum depth of binary tree (simple)

leetcode: 104. Maximum depth of binary tree

This problem can also be called recursively using dfs

111. Minimum depth of binary tree (simple)

For the maximum depth and minimum depth, you can also use hierarchical traversal (see what is the initialization definition of the first layer of depth)

Minimum depth traversal:
This question has one more judgment condition than the maximum depth. If it is null, it will be returned in time
leetcode: 111. Minimum depth of binary tree

The traversal of the minimum depth can be seen in the following problem solution (the problem solution comes from xcoder-4)

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // Calculate the depth of the left subtree
        int left = minDepth(root.left);
        // Calculate the depth of the right subtree
        int right = minDepth(root.right);
        // If the depth of the left or right subtree is not 0, that is, there is a subtree, then the minimum depth of the current subtree is the depth of the subtree + 1. That is to say, if one is 0, either left+1 or right+1
        // If the depth of both the left subtree and the right subtree is not 0, that is, both the left and right subtrees exist, then the minimum depth of the current subtree is their smaller value + 1
        return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
    }
}

Or this way of writing: (the solution comes from Hongsang)

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        else if (root.left == null) return minDepth(root.right) + 1;
        else if (root.right == null) return minDepth(root.left) + 1;
        else return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}

222. Number of nodes of complete binary tree (medium)*

Count the number of nodes
leetcode: 222. Number of nodes of complete binary tree

class Solution {
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }else {
            int a=countNodes(root.left);
            int b=countNodes(root.right);
            
            return a+b+1;
        }

    }
}

Breadth first traversal:

110. Balanced binary tree (simple)*

Title Link:
leetcode: 110. balanced binary tree

Bottom up recursion is a bit similar to post order traversal

class Solution {
    public boolean isBalanced(TreeNode root) {
        //The returned height must be a non negative integer. If abs is always greater than 1, there will be a negative number
        return heigh(root)>=0;

    }
    public int heigh(TreeNode root){
        if(root==null)return 0;

        //Recursive traversal from top to bottom, starting at the lowest level
        int left=heigh(root.left);
        int right=heigh(root.right);

        If the left subtree or right subtree is-1.Then recursion to the upper layer directly becomes-1. One more abs Directly greater than 1
        if(left==-1||right==-1||Math.abs(left-right)>1)return -1;

        //The largest one of the left and right subtrees returned upward, add 1 directly. Recursive condition
        return Math.max(left,right)+1;
    }
}

Or use top-down recursion:
(the code is hard to think about)

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
        //Always recurse the left and right subtrees, recurse down, take its maximum, and then add 1
            return Math.max(height(root.left), height(root.right)) + 1;
        }
    }
}

257. All paths of binary tree (simple)*

Title: leetcode: 257. All paths of binary tree

Idea:

class Solution {
    List<String> list=new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        
        //Propagate by String type
        backtrace(root,"");
        return list;
    }

    public void backtrace(TreeNode root,String sonpath){
        //Leaf nodes go back
        if(root==null)return;

        //StingBuilder in the previous path
        StringBuilder path=new StringBuilder(sonpath);
        path.append(Integer.toString(root.val));
        //Judge whether it is a leaf node. If it is a leaf node, it will be added to the list, and the StringBuilder added to the list will be converted to toString type
        if(root.left==null && root.right==null)list.add(path.toString());
        else{
            //Otherwise, append this symbol and trace back
            path.append("->");
            backtrace(root.left,path.toString());
            backtrace(root.right,path.toString());
        }

    }
}

The detailed explanation of this part can be seen as follows:

ACM player illustrates all paths of LeetCode binary tree (recursive + non recursive)

404. Sum of left leaves (simple)

Title: leetocde: 404. Sum of left leaves

Idea:

Logical sorting of hierarchical traversal

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
         if(root==null)return 0;

         Queue<TreeNode>que=new LinkedList<>();        
         int sum=0;

         que.offer(root);
         while(!que.isEmpty()){
             int n=que.size();
             for(int i=0;i<n;i++){
                TreeNode node=que.poll();

                //The main difficulty of this problem is the of the left leaf node. If it is a right leaf node (the first one in each layer), you cannot use hierarchy traversal, involving the parent node
                if(node.left!=null){
                    que.offer(node.left);
                    
                    //One more layer of judgment. If its grandson node is null, add its sum
                    if(node.left.left==null && node.left.right==null) sum+=node.left.val;
                }

                if(node.right!=null){
                    que.offer(node.right);
                }
             }
         }

         return sum;

    }
}

513. Find the value in the lower left corner of the tree (medium)

Title: leetcode: 513. Find the value in the lower left corner of the tree

Idea:

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        if(root==null)return 0;

        Queue<TreeNode> que=new LinkedList<>();
        //Record the value of the last node. Because it is a hierarchy traversal, the first node of the last layer must overwrite the previous value
        int res=0;

        que.offer(root);
        while(!que.isEmpty()){
            int n=que.size();
            for(int i=0;i<n;i++){
                TreeNode node=que.poll();
                if(i==0)res=node.val;
                if(node.left!=null){
                    que.offer(node.left);
                }
                if(node.right!=null){
                    que.offer(node.right);
                }
            }            
        
        }

        return res;
    }
}

112. Path sum (simple)

Title: leetcode: 112. Path sum

The general meaning is as follows: judge whether there is a path from the root node to the leaf node in the tree. The sum of all node values on this path is equal to the target and targetSum. If it exists, return true; Otherwise, false is returned.

A leaf node is a node that has no child nodes.

Idea:

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        
        //Recurse to the following. If root is null, false will be returned
        if(root==null)return false;
        
        //The value of root should be reduced for each layer
        targetSum-=root.val;

        //Judge whether the next layer is empty in advance, and its value is 0, and return true
        if(root.left==null && root.right==null && targetSum==0)return true;
        
        //Because it is a left-right subtree, you need to return to the selection of the left-right subtree
        if(root.left!=null){
            if(hasPathSum(root.left,targetSum))return true;
        }
        

        if(root.right!=null){
           if(hasPathSum(root.right,targetSum))return true; 
        }

        //If none is executed, false is returned
        return false;

               
    
    }
    
}

Or another way:

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        
        //Recurse to the following. If root is null, false will be returned
        if(root==null)return false;
        

        //Judge in advance whether the next level is empty and whether the current node is equal to the target value (this is not subtracted)
        if(root.left==null && root.right==null )return root.val==targetSum;
        
        //Because it is a left and right subtree, the selection of the left and right subtrees should be returned, and the value of each value should be subtracted
        if(root.left!=null){
            if(hasPathSum(root.left,targetSum-root.val))return true;
        }
        

        if(root.right!=null){
           if(hasPathSum(root.right,targetSum-root.val))return true; 
        }

        //If none is executed, false is returned
        return false;
       
    
    }
    
}

The above code logic can also be simplified:

class solution {
    public boolean haspathsum(Treenode root, int targetsum) {
        
        if (root == null) return false; // Empty exit
        
        // Leaf node to judge whether it meets
        if (root.left == null && root.right == null) return root.val == targetsum;

        // Find the path sum of branches on both sides
        return haspathsum(root.left, targetsum - root.val) || haspathsum(root.right, targetsum - root.val);
    }
}

Breadth first traversal:

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        //If it is empty in advance, false will be returned
        if (root == null) {
            return false;
        }

        //Create two queues or two stacks. One is used to store nodes and the other is used to store totals
        Queue<TreeNode> queNode = new LinkedList<TreeNode>();
        Queue<Integer> queVal = new LinkedList<Integer>();

        queNode.offer(root);
        queVal.offer(root.val);

        while (!queNode.isEmpty()) {

            TreeNode now = queNode.poll();
            int temp = queVal.poll();

            //Process the root node. If the next left and right nodes are null and the values have been equal in advance, return true
            if (now.left == null && now.right == null && temp==targetSum)return true;

            if (now.left != null) {
                queNode.offer(now.left);
                queVal.offer(now.left.val + temp);
            }
            if (now.right != null) {
                queNode.offer(now.right);
                queVal.offer(now.right.val + temp);
            }
        }
        return false;
    }
}

113. Path sum II (medium)

Title: leetcode: 113. Path sum II

The difference between this question and the previous one is that the general difference is as follows:

Idea:

The idea of backtracking recursion:

class Solution {
    List<List<Integer>> list=new ArrayList<List<Integer>>();
    LinkedList<Integer> sonlist=new LinkedList<>();
    
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if(root==null)return list;  

        backtrace(root,targetSum);
        return list;
        

    }
    public void backtrace(TreeNode root,int target){
        //If the boundary value exceeds, it will be returned. If the root is null, it will be returned to the previous layer
        if(root==null)return;

        //Whether or not, join the node first and judge later
        sonlist.addLast(root.val);  
        //After each node is added, it needs to be subtracted
        target-=root.val;

        //The judgment condition is not only 0, because to the leaf node, both the left and right nodes need to be null before adding
        if(target==0 && root.left==null && root.right==null){
            list.add(new ArrayList<>(sonlist));

        }
        
        //In the standard backtracking, if you don't reach the leaf node, you will always run around the node
        backtrace(root.left,target);
        backtrace(root.right,target);

        //If the execution fails, delete the leaf node
        sonlist.removeLast();
        //And add back the node just now
        target+=root.val;
    }
}

105. Construct binary tree from preorder and inorder traversal sequences (medium)

Title: leetcode: 105. Constructing binary tree from preorder and inorder traversal sequences

Idea:

Recursive call, distinguish the left and right subtrees, and its code logic
(3ms)

 //Preorder traversal and inorder traversal
 //By finding the first root node of preorder traversal (adding one by one in order), this function can be put on the logic of recursion
 //According to the value of the found root node, go through the middle order traversal to find the same subscript as the value of the root node
 //Length of left subtree: the number of all left subtrees is the subscript minus the point at the beginning of the middle order traversal. Length of right subtree: the length from subscript plus 1 to the end
class Solution {

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        //Recursive calls are made through two subtrees, that is, the range of two arrays
        return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
        

    }

    public TreeNode build(int []preorder,int p_start,int p_end,int [] inorder,int i_start,int i_end){
        //Because the initial value condition at the beginning is [0, n-1], it returns null as long as it exceeds the boundary
        if(p_start>p_end)return null;

        //Through the first node traversed in the previous order, find its value, and create a new point of the subtree
        int root_val=preorder[p_start];
        TreeNode root=new TreeNode(root_val);
        
        //Create an index value of the root node (this index corresponds to the root traversed in the middle order)
        int index=0;
        for(int i=i_start;i<=i_end;i++){
            if(root_val==inorder[i]){
                index=i;
                break;
            }
        }
        
        //Output the length of the left subtree, mainly for the subsequent recursive calls of the left and right subtrees
        int left=index-i_start;

        //Recursive call of left subtree and right subtree through its length
        //(first order left subtree, starting point + 1, starting point + left subtree length) (middle order left subtree, starting point, root node - 1)
        root.left=build(preorder,p_start+1,p_start+left,inorder,i_start,index-1);
        //(first order right subtree, starting point + left subtree length + 1) (middle order right subtree, root node + 1, end node)
        root.right=build(preorder,p_start+left+1,p_end,inorder,index+1,i_end);

        return root;

    }
}

For further optimization:
hashmap is used to store the values of each node traversed in the middle order (mainly to match the position of each initial root node in the first order)
(time 1ms)

For further optimization of the above code, you can see the solution to this question:
Detailed and popular thinking analysis, multi solution

106. Construct binary tree from middle order and post order traversal sequence (medium)

Title: leetcode: 106. Constructing binary tree from middle order and post order traversal sequences

Idea:

The general idea is very similar to the previous question
Just give some details here

This picture comes from
Graphic construction of middle order + post order of binary tree

class Solution {
    Map<Integer,Integer>map=new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }

        return build(inorder,0,inorder.length-1,postorder,0,postorder.length-1);

    }

    public TreeNode build(int []inorder,int i_start,int i_end,int []postorder,int p_start,int p_end){
        if(p_end<p_start)return null;

        int root_val=postorder[p_end];
        TreeNode root=new TreeNode(root_val);

        int index=map.get(root_val);
        int left=index-i_start;

        //The nodes of the left subtree in the subsequent order are (p_start, p_start+left-1)
        root.left=build(inorder,i_start,index-1,postorder,p_start,p_start+left-1);
        //The right subtree of the post order is (p_start+left,p_end-1)
        root.right=build(inorder,index+1,i_end,postorder,p_start+left,p_end-1);

        return root;
    }
}

654. Maximum binary tree (medium)

Title: leetcode: 654. Maximum binary tree

Here is a binary search that cannot be used (binary search is ordered or partially ordered, which is unordered)

class Solution {
    //List<Integer> list=new ArrayList<>();
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return  ss(nums,0,nums.length-1);

        
    }
    public TreeNode ss(int []nums,int left,int right){
        if(left>right)return null;

        
        //Find the subscript value of the largest node. The maximum subscript given at the beginning is the leftmost
        int maxid=left;
        for(int i=left;i<=right;i++){
            //Judge the comparison value between its value and each subscript one by one, and then overwrite the value of the maximum subscript. (the subscript value is traversed from small to large, so it will not be confused, and the next i will also be + 1)
            if(nums[i]>nums[maxid])maxid=i;
        }
        //The maximum value of each node is new
        TreeNode root =new TreeNode(nums[maxid]);

        // Wrong usage. Instead of finding the intermediate node, find the largest node. Similar to fast scheduling idea
        // int mid=left+(right-left)/2;
        //list.add(nums[mid]);

        //Traverse left and right nodes
        root.left=ss(nums,left,maxid-1);
        root.right=ss(nums,maxid+1,right);


        return root;
        
    
    }
}

617. Merge binary tree (simple)

Title: leetcode: 617. Merge binary tree

It roughly means merging two binary trees

Idea:

The following is the preorder traversal. You can also change some nodes to medium order or post order

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1==null)return root2;
        if(root2==null)return root1;
        
        root1.val=root1.val+root2.val;
        root1.left=mergeTrees(root1.left,root2.left);
        root1.right= mergeTrees(root1.right,root2.right);

        return root1;
    }
}

If you do not change the node information, you can also create a temporary binary tree

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1==null)return root2;
        if(root2==null)return root1;
        
        //Create a temporary binary tree. The specific changes are here
        TreeNode root=new TreeNode(0);
        root.val=root1.val+root2.val;
        root.left=mergeTrees(root1.left,root2.left);
        root.right= mergeTrees(root1.right,root2.right);

        return root;
    }
}

The same is true for hierarchical traversal. The code is shown here

class Solution {
    // Use queue iteration
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) return root2;
        if (root2 ==null) return root1;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root1);
        queue.offer(root2);

        while (!queue.isEmpty()) {
            TreeNode node1 = queue.poll();
            TreeNode node2 = queue.poll();

            // At this time, the two nodes are not necessarily empty
            node1.val = node1.val + node2.val;
            
            // If the left node of both trees is not empty, join the queue
            if (node1.left != null && node2.left != null) {
                queue.offer(node1.left);
                queue.offer(node2.left);
            }
            // If the right node of both trees is not empty, join the queue
            if (node1.right != null && node2.right != null) {
                queue.offer(node1.right);
                queue.offer(node2.right);
            }
            // If the left node of node1 is empty, assign a value directly
            if (node1.left == null && node2.left != null) {
                node1.left = node2.left;
            }
            // If the left node of node2 is empty, assign a value directly
            if (node1.right == null && node2.right != null) {
                node1.right = node2.right;
            }
        }
        return root1;
    }
}

Binary search tree

nature:

  • The element values of all nodes in the left subtree are less than those of the root;
  • The element value of all nodes in the right subtree is greater than that of the root.

If you want to search for an edge, the recursive function needs to add the return value. Because there is a target node, you need to return
Without return is to traverse the whole tree

While explaining the binary search tree, first reply to the recursion and iteration of the binary tree (middle first, then level traversal)
Recursion is explained here

class Solution {
    // Recursive, ordinary binary tree
    public TreeNode searchBST(TreeNode root, int val) {
    	//If the left node asks null or equal, it directly returns root
        if (root == null || root.val == val) {
            return root;
        }
        
        //Recursive left node
        TreeNode left = searchBST(root.left, val);
        //If the left node is not empty, the left node is returned
        if (left != null) {
            return left;
        }
        return searchBST(root.right, val);
    }
}

700. Search in binary search tree (simple)

Title: leetcode: 700. Search in binary search tree

The general meaning is as follows:
Given the root node root of binary search tree (BST) and an integer value val.

You need to find the node with node value equal to val in BST. Returns the subtree with this node as the root. If the node does not exist, null is returned.

Idea:

recursion

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        
        //The following two cases can be combined and directly returned to root
        // if(root==null)return null;
        // if(root.val==val)return root;

        if(root==null || root.val==val)return root;

        if(root.val>val)return searchBST(root.left,val);
        else if(root.val<val) return searchBST(root.right,val);

        // return root;  // This is what it says when there is no initial condition for merging
        return null;


    }
}

Directly through iteration:

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

        return null;

    }
}

98. Verify binary search tree (medium)

Title: leetode: 98. Validate binary search tree

Idea:
There is a minimum value of int in the test data, so it is defined as the type of long long and initialized as the minimum value of long.
Memorize a smallest node through comparison

class Solution {
    //The test data itself is smaller than the int data, so it is defined as long type
    long pre=Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        //Recursion from bottom to top. It is true when it is null
        if(root==null)return true;

        //Left node recursion
        boolean left=isValidBST(root.left);

        //If the root node is processed in order, remember that pre is the previous node and traversal to the last is in order, which is a binary search tree
        //Use pre to remember the previous node
        if(root.val>pre)pre=root.val;
        //If not, false will be returned in advance, and there is no need to search the right subtree
        else return false;


        boolean right=isValidBST(root.right);

        return left&&right;
    }
}

There may be smaller nodes, so it is directly defined as null
The details are as follows:

530. Minimum absolute difference of binary search tree (simple)

Title: leetcode: 530. Minimum absolute difference of binary search tree

Idea:

Recursive thinking:

class Solution {
    //Because the minimum value of the node in the data is more than 0, the initialized minimum value node needs any negative number
    int pre=-1;
    //Traverse the minimum node
    int ans=Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {    
        
        if(root==null)return 0;

        min(root);

        return ans;

    }
    public void min(TreeNode root){
        //The middle order traversal is adopted to traverse to the leaf node, that is, back plastic
        if(root==null)return ;

        min(root.left);

        //Process the root node, recurse to the first node in the last process at the beginning, and assign the value of its node to pre
        //If this is not done, the value of pre will always be the minimum
        if(pre==-1){
            pre=root.val;
        }else {
            ans=Math.min(ans,root.val-pre);
            pre=root.val;
        }
        

        min(root.right);


    }
}

In order to avoid this situation, the minimum node is not defined directly:

General idea:
Define a pre to save the previous node
When recursing to the first root node, pre is not null, and it is also ingenious to save the value of the root node
Moreover, to find the point of absolute value, the binary search tree is the previous node minus the last saved node (medium order traversal)

501. Mode in binary search tree (simple)*

Title: leetcode: 501. Mode in binary search tree

If there is more than one mode in the tree, it can be returned in any order.

Idea:

class Solution {
    //Define a list to add all large numbers, that is, the numbers with more modes
    List <Integer>list=new ArrayList<>();
    //Statistics
    int maxcount=0;
    int count=0;
    //Saves the value of the previous node
    TreeNode pre=null;

    public int[] findMode(TreeNode root) {
        if(root==null)return new int[0];
        

        find(root);

        //Convert all the nodes in the list into arrays, and then output them in the form of arrays
        int [] res=new int [list.size()];
        for(int i=0;i<res.length;i++){
            res[i]=list.get(i);
        } 

        return res;


    }
    public void find(TreeNode root){
        if(root==null)return ;

        find(root.left);

        //The following are the processing results of the root node
        //Because the binary search tree has been arranged in order, the use of medium order traversal is sequential by default. If it is not equal, directly change its number to 1. If it is equal, add 1 to the number

        if(pre!=null && pre.val!=root.val){
            count=1;
        }else {
            count++;
        }

        //After making statistics, compare with the largest number
        //If the current number is the largest number, clear all nodes in the list, add the current node, and update the largest node

        if(count>maxcount){
            list.clear();
            list.add(root.val);
            maxcount=count;

        //At the beginning, when both are 0, the first node will be added, which just meets the situation
        //Another special case is that the modes are equal
        }else if(count==maxcount){
            list.add(root.val);
        }

        //Save previous node
        pre=root;

        find(root.right);
    }
}

236. Nearest common ancestor of binary tree (medium)

Title: leetcode: nearest common ancestor of binary tree

Idea:

To return its public nodes upward, traverse from bottom to top, and return node values. Post order traversal is used by default (it has the idea of backtracking)

See the illustration of [code recall]:

The idea of recursive construction:
The specific codes are as follows

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //The two initial conditions are either null or equal to p or q
        //This is the judgment at the beginning of recursion

        //Judge whether the left and right nodes are null. If they are returned, they will be null
        if(root==null)return null;
        //If the judged node itself has an equal value, it will be returned as itself first. You don't have to judge leaf nodes anymore
        if(root==p||root==q)return root;

        //If the above conditions are not met, it will be traversed through recursion, so the left node is recursive first and the right node is recursive
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);

        //For the judgment after recursion, the leaf node itself is null, and the initial judgment conditions have been passed back
        //If the left return is null, it means that the value is not equal or it is a leaf node. Returns the value of the right node directly. The same is true for the right node
        //If you don't want to wait left or right, the returned value is itself, that is, in the subtree of 2, 7 and 4, the left node of 2 is 7 and the right node is 4. Then return 2
        if(left==null)return right;
        else if (right==null)return left;
        else return root;
        
    }
}

235. Nearest common ancestor of binary search tree (simple)

Title: leetcode: 235. Nearest common ancestor of binary search tree

Idea:

This problem can also be solved by using the solution of the previous problem
(time 7ms)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)return null;
        if(root==p|root==q)return root;

        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);

        if(left==null)return right;
        else if(right==null)return left;
        else return root;
    }
}

But it's a little complicated
Because it is a search tree

You can traverse its nodes left and right by judging
If equal, just return to root directly
(time 6ms)

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);
        else if(root.val<p.val&&root.val<q.val)return lowestCommonAncestor(root.right,p,q);
        
        return root;
    }
}

Using this method will directly timeout

Therefore, modify the logic: (time 5ms)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(true){
            if(root.val>p.val&&root.val>q.val){
                root=root.left;
            }
            else if(root.val<p.val&&root.val<q.val){
                root=root.right;
            }else {
                break;
            }
        }
        
        return root;
    }
}

701. Insert operation in binary search tree (medium)

Title: leetcode: 701. Insertion operation in binary search tree

Idea:

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        //If you go here and find it empty, you can create a node value
        if(root==null)return new TreeNode(val);

        //If the left and right nodes are different, you can re point through the left and right nodes in root to recursively create the left and right subtrees
        //This question cannot use return to return the previous node, because the output is a complete tree with a pointing tree
        if(root.val>val)root.left= insertIntoBST(root.left,val);
        else if(root.val<val) root.right= insertIntoBST(root.right,val);

        //Return to the modified root node
        return root;

    }
}

Using simulation algorithms:

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        //First judge whether the initial value is null. If it is null, directly create a node value
        if (root == null) {
            return new TreeNode(val);
        }
        
        //Traversal using temporary nodes
        TreeNode node=root;
        //The general condition is that the node is not null and is traversed all the time
        while(node!=null){
            //The condition of refinement is to judge the direction
            if(node.val>val){
                //Every time you add, you should judge whether it is null. If it is null, it will directly point to the new node
                if(node.left==null){
                    node.left=new TreeNode(val);//
                    break;
                }else{
                    //If it is not null, point to the old node
                    node=node.left;
                }
            //The idea is the same as above
            }else if(node.val<val){

                if(node.right==null){
                    node.right=new TreeNode(val);
                    break;
                }else {
                    node=node.right;
                }
            }

        }

        return root;

    }
}

450. Delete nodes in binary search tree (medium)*

Title: leetocde: 450. Delete node in binary search tree

Idea:
The specific ideas are as follows:
It's important to know how to delete
If you don't understand the code logic, you can read the explanation of the code Capriccio:
450. Delete nodes in binary search tree

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) { 
        //1. The deleted node is not found. Traverse to the empty node and return directly
        if(root==null)return null;

        //Itself is a binary search tree
        if(root.val>key){
            root.left=deleteNode(root.left,key);
        }else if(root.val<key){
            root.right=deleteNode(root.right,key);
        }else if(root.val==key){
            //2. The left child is empty and the right child is not empty. Delete the node, fill in the right child, and return the right child as the root node
            if(root.left==null)return root.right;
            //3. The right child is empty and the left child is not empty. Delete the node, fill in the left child, and return the left child as the root node
            if(root.right==null)return root.left;

            //4. If the left and right child nodes are not empty, place the left subtree of the deleted node at the left child of the leftmost node of the right subtree of the deleted node (key understanding)
            //Step right first, from left to tail
            TreeNode temp=root.right;
            while(temp.left!=null){
                temp=temp.left;
            }
            //Use the root node to save the value of the temp node and redirect the root node to
            root.val=temp.val;

            //The right child of the deleted node is the new root node
            root.right=deleteNode(root.right,temp.val);
        }

        //Return the re established node root
        return root;

    }
}

669. Pruning binary search tree (medium)

Title: leetcode: 669. Pruning binary search tree

(it is a binary search tree in itself, so you only need to delete unnecessary nodes)
The general meaning is as follows:

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        //If the node does not exist, you can directly return null
        if(root==null)return null;

        //Considering that it is troublesome to delete binary search tree and deal with more data, the reverse aspect is considered. Direct the dissatisfied to the other side

        if(root.val<low){
        //If not, crop the left node and return to its right node
            return trimBST(root.right,low,high);
        }else if(root.val>high){
        //If it is not in this range, crop the right node and return to its left node
            return trimBST(root.left,low,high);
        }

        //Traverse the nodes that meet the conditions, point their left node to the left node, and point to the right node if they point to the right node
        root.left=trimBST(root.left,low,high);
        root.right=trimBST(root.right,low,high);

        //Returns the node to which root redirects
        return root;

    }
}

108. Convert an ordered array into a binary search tree (simple)*

Title: leetcode: 108. Convert an ordered array into a binary search tree

Idea:

The essence is to find the segmentation point, which is used as the current node, and then recurse the left interval and right interval.

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        //Left closed right closed interval
        return ss(nums,0,nums.length-1);
    }
    public TreeNode ss(int []nums,int left,int right){
        //If left is greater than right, a null node is returned first
        if(left>right)return null;

        //Binary search of its nodes is ordered in itself, so check the left subtree through the node on the left and the right subtree through the node on the right
        int mid=left+(right-left)/2;
        //There is no subtree structure in itself, so you need to create
        TreeNode root=new TreeNode(nums[mid]);
        root.left=ss(nums,left,mid-1);
        root.right=ss(nums,mid+1,right);

        return root;
    }
}

538. Convert binary search tree to cumulative tree (medium)

Title: leetcode: 538. Convert binary search tree into cumulative tree

Roughly as follows:

Idea:

class Solution {
    //Define a count
    int sum=0;

    //The cumulative tree here is actually anti middle order traversal
    public TreeNode convertBST(TreeNode root) {
        //If it is empty, an empty node is returned
        if(root==null)return null;

        convertBST(root.right);

        //Specifically, the root node is processed. After accumulation, it is stored back to the root node
        sum+=root.val;
        root.val=sum;
        convertBST(root.left);

        return root;

    }
}

Tags: Java Algorithm leetcode

Posted by XPertMailer on Wed, 20 Apr 2022 08:16:34 +0300