# preface

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

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;
}
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);
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);
}
}
```

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

TreeNode node = root;
while (node != null||!stack.isEmpty() ) {
while (node != null) {
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<>();

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

stk.push(root);
root = root.left;

}

root = stk.pop();
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;

//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){
//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;

que.offer(root);
while(!que.isEmpty()){

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

}
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;
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

//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;
}

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);

}
}
```

```class Solution {
public boolean isSymmetric(TreeNode root) {

return ss(root,root);

}
//The returned type is boolean
public boolean ss(TreeNode L1,TreeNode L2){
//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;
}

}
}
```

## 110. Balanced binary tree (simple)*

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)*

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

Idea:

Logical sorting of hierarchical traversal

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

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)

Idea:

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

//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);
}
}
```

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

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)

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>>();

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
//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){

}

//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)

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)

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)

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;

//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)

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.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)

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)

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)

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)*

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();
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){
}

//Save previous node
pre=root;

find(root.right);
}
}
```

## 236. Nearest common ancestor of binary tree (medium)

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)

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
(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)

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 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)*

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)

(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)*

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)

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;

}
}
```

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