# Algorithm exercise 19: search Binary Tree

2022-01-27 02:39:54

`````` Give you the root node of a binary tree  root , Determine whether it is an effective binary search tree .
It works   The binary search tree is defined as follows ：
The left subtree of the node contains only   Less than   Number of current nodes .
The right subtree of the node contains only   Greater than   Number of current nodes .
All left and right subtrees themselves must also be binary search trees .
```

1.
2.
3.
4.
5.
```

`````` Input ：root = [2,1,3]
Output ：true
```

1.
2.
```

`````` Input ：root = [5,1,4,null,null,3,6]
Output ：false
explain ： The value of the root node is  5 , But the value of the right child node is  4 .
```

1.
2.
3.
```
``````package com.example.springboot;

import java.util.*;
public class Test2 {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode() {
}

TreeNode(int val) {
this.val = val;
}

TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
// Search binary trees
public boolean isValidBST(TreeNode root) {
return   isSearch(root).isBST;
}
public Info isSearch(TreeNode root){
// If the binary tree is empty , return null
if(root==null){
return  null;
}
Info searchLeft = isSearch(root.left);
Info searchRight = isSearch(root.right);
// Set the maximum and minimum values to be the current values
int max=root.val;
int min= root.val;
// If the left node is not empty , Find the maximum and minimum values of the left node
if(searchLeft!=null){
max=Math.max(max, searchLeft.max);
min=Math.min(min,searchRight.min);
}
// If the right node is not empty , Find the maximum and minimum values of the right node
if(searchRight!=null){
max=Math.max(max,searchRight.max);
min=Math.min(min,searchRight.min);
}
// If the maximum value of the left node is less than the current value , And the minimum value on the right is greater than the current node , Then the search tree conditions are met
boolean isBST=true;
if(searchLeft!=null && !searchLeft.isBST){
isBST=false;
}
if(searchRight!=null && !searchRight.isBST){
isBST=false;
}
return new Info(isBST,max,min);
}
public class Info{
public boolean isBST;
public int max;
public int min;
public Info(boolean isBST,int max,int min){
this.isBST=isBST;
this.max=max;
this.min=min;
}
}

}
```

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
```