## 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