二叉搜索树（Binary Search Tree）定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

再刷一遍二叉搜索树

（一）

230. 二叉搜索树中第K小的元素

230. 二叉搜索树中第K小的元素
给定一个 二叉搜索树 的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

1. 二叉搜索树 中序遍历的序列，就是一个升序的序列。
2. 解决这个问题，只要进行中序遍历，得到第 k 个值赋给 res 就可以了

int res = 0;
int index = 0;
public int kthSmallest(TreeNode root, int k) {traverse(root, k);return res;
}//中序遍历，将第 k 个值赋给 res 
public void traverse(TreeNode root, int k){if(root == null) return;traverse(root.left, k);index++;if(index == k){res = root.val;return;}traverse(root.right, k);
}

538. 把二叉搜索树转换为累加树

538. 把二叉搜索树转换为累加树
给出 二叉搜索树 的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

//原二叉搜索树的最右叶子节点的节点值最大
public TreeNode convertBST(TreeNode root) {traverse(root);return root;
}
int sum = 0;
public void traverse(TreeNode root){if(root == null) return;//从右节点开始累加traverse(root.right);sum = sum + root.val;root.val = sum;traverse(root.left);return;
}

---

（二）

98. 验证二叉搜索树

98. 验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

//每一个节点都要考虑应该大于 [?] 小于 [?]
public boolean isValidBST(TreeNode root) {return isTrue(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
//力扣测试时可能会有测试数据越界，可将 int 改为 long
public boolean isTrue(TreeNode root, int min, int max){if(root == null) return true;if(root.val <= min || root.val >= max)return false;//左子树的最大值为当前节点的值，右子树的最小值为当前节点的值return isTrue(root.left, min, root.value) && isTrue(root.right, root.val, max);
}

700. 二叉搜索树中的搜索

700. 二叉搜索树中的搜索
给定 二叉搜索树 的根节点和一个值。 你需要在BST中找到 节点值等于给定值 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

1. 最简单的办法，直接遍历找就可以了。
2. 在此基础上我们还可以根据二叉搜索树的性质来减少搜索。

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

701. 二叉搜索树中的插入操作

701. 二叉搜索树中的插入操作
给定 二叉搜索树 的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

1. 找到正确的位置，将值插入二叉搜索树

public TreeNode insertIntoBST(TreeNode root, int val) {if(root == null) return newTreeNode(val);if(root.val > val)root.left = insertIntoBST(root.left, val);if(root.val < val)root.right = insertIntoBST(root.right, val);return root;
}

450. 删除二叉搜索树中的节点

450. 删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

1. 删除节点，首先要找到节点。寻找给定值的节点即上题 700.二叉搜索树中的搜索，很简单。

2. 找到后会有这几种情况。
   ① 该节点无左右子节点，可直接删除。
   ② 该节点有左子节点或右子节点，那么删除此节点后，需要让左子节点或右子节点代替被删除节点的位置。
   ③ 该节点有左子节点和右子节点，那么删除后还需判断让谁来接替自己的位置。【回忆一下二叉搜索树的特点，右节点 > 根节点 > 左节点，那么删掉根节点后，要找右节点的最小值（或者左节点的最大值）作为根节点】

3. 先根据 700题 写出框架，再考虑细节问题。

public TreeNode deleteNode(TreeNode root, int key) {if(root == null) return null;if(root.val == key){//三种情况//1.无左右子节点if(root.left == null && root.right == null) return null;//2.有左子节点或右子节点if(root.left == null) return root.right;if(root.right == null) return root.left;//3.有左子节点和右子节点，寻找右子树的最小值作为根节点if(root.left != null && root.right != null){TreeNode minNode = getMin(root.right);root.val = minNode.val;//将右子树中值为minNode.val的节点删除root.right = deleteNode(root.right, minNode.val);}}else if(root.val > key){root.left = deleteNode(root.left, key);	}else if(root.val < key){root.right = deleteNode(root.right, key);}return root;
}
//寻找最小值
public TreeNode getMin(TreeNode node){//最左的叶子节点是最小的while(node.left != null) node = node.left;return node;
}

---

（三）

96. 不同的二叉搜索树

96. 不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

1. 构造一个二叉树，要先考虑根节点。显然此题中 [1,n] 每个数都可以作为根节点。
2. 遍历每个数作为根节点的情况。
3. 假如取 x 作为根结点，那么计算这种情况的个数，就看左右子树分别能组成多少不同的二叉树。根节点能组成的情况等于 left ✖ right
4. left = count ( lo, x-1)，right = count ( x+1, hi )
   【函数 count( int lo, int hi ) 计算[lo, hi] 能组成多少不同的二叉树。】
5. 所以此题是遍历加递归，还存在着重叠子问题。

public int numTrees(int n) {return count(1, n);
}
public int count(int lo, int hi){//存在递归，记得写跳出递归的条件if(lo > hi) return 1;//遍历 [lo - hi]int res = 0;for(int i=lo; i<=hi; i++){int left = count(lo, i-1);int right = count(i+1, hi);res += left * right;}return res;
}

上面的解法没有解决重叠子问题，只是用穷举解决的。
使用动态规划解法，自底向上的解决问题。

1. 根据题目看，决定不同二叉树个数的是数组长度，而不是数组内容。
2. 确定dp[]数组，dp[0] = 1、dp[1] = 1、dp[2] = 2 …，求出dp[n]

public int numTrees(int n) {int[] dp = new int[n + 1];dp[0] = 1;dp[1] = 1;//计算dp[i]，直到求出dp[n]for (int i = 2; i <= n; ++i) {//遍历分别以这个数组中的数做根节点的不同二叉树的个数，最后累加得到dp[i]//长度为 i, 让 j 做根节点，左边数组长度为[j-1]，右边数组长度为[i-j]for (int j = 1; j <= i; ++j) {//dp[i] = 这些遍历的累加dp[i] += dp[j - 1] * dp[i - j];}}return dp[n];
}

95. 不同的二叉搜索树 II

95. 不同的二叉搜索树 II
给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

1. 穷举出所有的根节点
2. 递归构造出所有左右子树【List< TreeNode > 类型】
3. 利用循环使根节点，连接这些所有的子树

public List<TreeNode> generateTrees(int n) {return build(1,n);
}
public List<TreeNode> build(int lo, int hi){List<TreeNode> res = new LinkedList<>();if(lo > hi){res.add(null);return res;}// 穷举 root 节点的所有可能。for(int i=lo; i<=hi; i++){List<TreeNode> lefts = build(lo, i-1);List<TreeNode> rights = build(i+1, hi);// 递归构造出左右子树的所有合法 BST。for(TreeNode left : lefts ){for(TreeNode right : rights){//使用这些左右子树构造二叉树TreeNode root = new TreeNode(i);root.left = left;root.right = right;res.add(root);}}}        return  res;
}

---

感谢看到这里😛😛，快去多刷题吧。看的再多，不如沉下心去试一试呀😎