# 1. 二叉搜索树
二叉搜索树 (Binary Search Tree) (opens new window),又被称为二叉排序树，二叉查找树。 其特点是：
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为二叉搜索树；
二叉搜索树(BST)的中序遍历得到的序列是递增的。(解题常备)
相较于其他数据结构，二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。最优是O(log n),最差是O(n)
# 2. Leetcode的相关题目
700. 二叉搜索树中的搜索 - E (opens new window)
一提到二叉树遍历的迭代法，可能立刻想起使用栈来模拟深度遍历，使用队列来模拟广度遍历。
但对于二叉搜索树可就不一样，由于二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。
654. 最大二叉树 - M (opens new window)
具体看题目，就会发现其实是二叉搜索树的构建。
998. 最大二叉树 II - M (opens new window)
这道题目跟654的差不太多，但是题目描述有点绕，云里雾里的。 大致题意:给你一个已经构造好的最大二叉树，根据654题的描述，这个最大二叉树是对应一个数组的，现在在这个数组后面append一个元素val，然后重新构造一个最大二叉树。
思路：
1、一定先复习一下654题，理解如何从数组A构造最大二叉树的。
2、B是在A的最后添加了一个val，这个位>置非常关键，有两种可能： a、val是B中最大的，说明它是新树的root，原来的树全部变为val的左子树，val右边没有值了，所以右子树为空。 b、val不是最大，因为它的位置在最大值右边最后一个，所以只能是右子树的某个节点，并且该节点右孩子一定为空。
# 3. 解法说明
# 3.1 验证二叉搜索树
98. 验证二叉搜索树 - M (opens new window)
凡是出现二叉搜索树,一定要反应出来:二叉搜索树的中序序列是递增的,我们可以借助于这一个性质来解题。(另外需要强调一点，BST不允许有重复元素)
另外也可以根据其定义来解题。
# 3.1.1 解法1
根据二叉搜索树的中序序列是递增有序的的性质来解题。
public class Solution{
List<Integer> list = new ArrayList();
public boolean isValidBST(TreeNode root) {
if(root == null){
return true;
}
inorder(root);
if(list.size <= 1){
return true;
}
for(int i = 1; i < list.size(); i++){
if(list.get(i) <= list.get(i-1)){
return false;
}
}
return true;
}
public void inorder(TreeNode root){
if(root == null) return;
inorder(root.left);
list.add(root.val);
inorder(root.right);
}
}
其实上面的解法是额外借助空间来判断是否有序，其实还有更简洁的写法。只需要保存每次遍历的前一个值即可。
public class Solution{
// 这里为啥采用Long呢？因为测试用例需要覆盖。
// 这里为啥要用最小值呢？因为BST的中序序列是递增的。即前一个比后一个小。
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if(root == null){
return true;
}
if(isValidBST(root.left)){
if(pre < root.val){
pre = root.val;
return isValidBST(root.right);
}
}
return false;
}
}
# 3.1.2 解法2
根据二叉搜索树的性质来解题。即：左子树节点 < 根节点 < 右子树节点
public class Solution{
public boolean isValidBST(TreeNode root){
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean isValidBST(TreeNode root, long min, long max){
if(root == null){
return true;
}
// 这里的"="必须有，因为BST不允许有重复值
if(root.val <= min || root.val >= max){
return false;
}
// 这里注意判断左右子树时，min,max值的变化。
return isValidBST(root.left,min,root.val) && isValid(root.right,root.val,max);
}
}
# 3.2 二叉搜索树中的搜索
700. 二叉搜索树中的搜索 - E (opens new window)
一提到二叉树遍历的迭代法，可能立刻想起使用栈来模拟深度遍历，使用队列来模拟广度遍历。
但对于二叉搜索树可就不一样，由于二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。
# 3.2.1 解法1(递归)
利用二叉搜索树的性质来进行解题。
public class Solution{
public TreeNode searchBST(TreeNode root, int val) {
if(root == null || root.val == val){
return root;
}
if(val > root.val){
root = searchBST(root.right,val);
}else{
root = searchBST(root.left,val);
}
return root;
}
}
# 3.2.2 解法2(迭代)
public class Solution{
public TreeNode searchBST(TreeNode root,int val){
if(root == null || root.val == val){
return root;
}
while(root != null && root.val != val){
if(val > root.val){
root = root.right;
}else{
root = root.left;
}
}
return root;
}
}
# 3.3 二叉搜索树中的插入操作
701. 二叉搜索树中的插入操作 -M (opens new window)
见到二叉搜索树的题目,就从其性质和**特点(中序递增)**这两点入手即可
# 3.3.1 解法1
public class Solution{
public TreeNode insertIntoBST(TreeNode root, int val) {
// 1. 如果树为空，直接创建根节点并返回即可
if(root == null){
return new TreeNode(val);
}
// 2. 根据其性质来进行左右子树的操作。
if(root.val < val){
root = insertIntoBST(root.right, val);
}else{
root = insertIntoBST(root.left, val);
}
return root;
}
}
# 3.3.2 解法2
很容易看明白，对于二叉搜索树的题目，迭代跟递归的区别不是那么明显。
public class Solution{
public TreeNode insertIntoBST(TreeNode root, int val){
if(root == null){
return new TreeNode(val);
}
TreeNode cur = root;
while(cur != null){
if(cur.val < val){
if(cur.right != null){
cur = cur.right;
}else{
cur.right = new TreeNode(val);
break;
}
}else{
if(cur.left != null){
cur = cur.left;
}else{
cur.left = new TreeNode(val);
break;
}
}
}
return root;
}
}