Question 1: Question 617 of force deduction

Problem solving ideas:

reference This article

The code is as follows:

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null) {
            return root2;
        }
        if(root2 == null) {
            return root1;
        }
        TreeNode root = new TreeNode(0);
        root.val = root1.val + root2.val;//in
        root.left = mergeTrees(root1.left, root2.left);//Left
        root.right = mergeTrees(root1.right, root2.right);//right
        return root;
    }
}

Question 2: Force deduction 700 questions

Problem solving ideas:

According to the characteristics of binary search tree, see This article

The code is as follows:

Method 1: recursion

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null || root.val == val) {
            return root;
        }
        //According to the characteristics of binary search tree
        //If the value of root is greater than the given value, it means that the value to be found is on the left of root, so let's go to the left and find it
        if(root.val > val) {
            return searchBST(root.left, val);
        }
        //Similarly
        if(root.val < val) {
            return searchBST(root.right, val);
        }
        return null;
    }
}

Mode 2: iteration

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

Question 3: Force deduction 98 questions

Problem solving ideas:

First, what does BST look like? It's orderly, isn't it; Let's talk about the way we traverse the binary tree. What is order? Is it medium order traversal. We only need to judge whether the middle order traversal array increases monotonically from left to right!

The code is as follows:

class Solution {
    TreeNode pre = null;
    public boolean isValidBST(TreeNode root) {
        //It's better not to use the maximum variable to record, because we don't know whether the minimum value in the test case is int or long
        //Let's use a pointer to record the previous value
        if(root == null) {
            return true;
        }
        boolean left = isValidBST(root.left);//Judge left tree
        if(pre != null && pre.val >= root.val) {
            return false;
        }
        pre = root;
        boolean right = isValidBST(root.right);//Judge right tree
        return left && right;
    }
}

Question 4: Force deduction 530 questions

Problem solving ideas:

Similarly, the minimum value of any two differences in the middle order traversal + comparison ordered array is used

The code is as follows:

class Solution {
    TreeNode pre = null;
    int res = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
        if(root == null) {
            return 0;
        }
        traversal(root);
        return res;
    }
    //Traverse all, no return value is required
    private void traversal(TreeNode t) {
        if(t == null) {
            return;
        }
        traversal(t.left);//Left tree
        if(pre != null) {
            res = Math.min(res, t.val - pre.val);//Record minimum
        }
        pre = t;//Record previous position
        traversal(t.right);//Right tree
    }
}

There are also several questions:
Force deduction question 501
Force deduction 236 questions
Force deduction 235 questions
Force deduction question 701

Question 5: Force deduction 450 questions

Problem solving ideas:

reference resources mogul The train of thought, Gaga drop!!!
There are five situations:
The first case: if the deleted node is not found, it returns directly after traversing the empty node
Found deleted node
The second case: if the left and right children are empty (leaf node), delete the node directly and return NULL as the root node
When deleting a child node, the child node is left blank and the right node is left blank. When deleting a child node, the child node is returned to the right node
The fourth case: the right child of the deleted node 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
The fifth case: if the left and right child nodes are not empty, put the head node (left child) of the left subtree of the deleted node on the left child of the leftmost node of the right subtree of the deleted node, and return the deleted node. The right child is the new root node.
I have to learn more from others. How long will it take me to figure it out? Woo woo woo

The code is as follows:

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        //1
        if(root == null) {
            return root;
        }
        
        if(root.val == key) {
            //2
            if(root.left == null && root.right == null) {
                return null;
                //3
            } else if(root.left == null) {
                return root.right;
                //4
            } else if(root.right == null) {
                return root.left;
                //5
            } else {
                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;
    }
}

Similarly, there are the following questions:
Force deduction 669 questions

Question 6: Force deduction 108 questions

Problem solving ideas:

This question is less than question 654 in the process of traversing the tree. Other questions are no different. It also starts from the middle of the array as the root node to form a new tree. The left side of the root node and the right side of the root node are recursive until the array left > = right is satisfied (this is the case of left closing and right opening).

The code is as follows:

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        //Left closed right open
        TreeNode root = traversal(nums, 0, nums.length);
        return root;
    }
    private TreeNode traversal(int[] nums, int left, int right) {
        if(left >= right) {
            return null;
        }
        //At this time, there is only one, special judgment
        if(right - left == 1) {
            return new TreeNode(nums[left]);
        }
        int mid = left + ((right - left) / 2);
        TreeNode root = new TreeNode(nums[mid]);
        root.left = traversal(nums, left, mid);
        root.right = traversal(nums, mid + 1, right);
        return root;
    }
}

Question 7: Force deduction 538 questions

Problem solving ideas:

What is a cumulative tree? It is to make a tree into an array according to the order of right, middle and left, and add up the numbers in turn to form a new tree, first right, then middle, then left, okkk!

The code is as follows:

class Solution {
    int pre;//Define a parameter to record the value of the previous node of cur
    public TreeNode convertBST(TreeNode root) {
        pre = 0;
        traversal(root);
        return root;
    }
    private void traversal(TreeNode cur) {
        if(cur == null) {
            return;
        }
        traversal(cur.right);//right
        cur.val = cur.val + pre;//in
        pre = cur.val;
        traversal(cur.left);//Left
    }
}

At this point, the topic of binary tree will come to an end. Come back and have a look at your problems when you brush the second time! Ha ha ha