数据结构——二叉树——二叉搜索树（Binary Search Tree, BST）

一、98. 验证二叉搜索树

二、96. 不同的二叉搜索树

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

二叉搜索树：对于二叉搜索树中的每个结点，其左子结点的值小于该结点的值，而右子结点的值大于该结点的值

一、98. 验证二叉搜索树

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

有效二叉搜索树定义如下：

节点的左
子树
只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：
输入：root = [2,1,3]
输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：

树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

分析：

class Solution {public boolean isValidBST(TreeNode root) {return isBST(root, Long.MIN_VALUE, Long.MAX_VALUE); // 初始时，上下界分别为长整型的最小值和最大值}public boolean isBST(TreeNode root, long min, long max) {if (root == null) {return true; // 空节点符合二叉搜索树的定义}if (root.val <= min || root.val >= max) {return false; // 如果当前节点的值不在允许的范围内，则不是二叉搜索树}// 递归检查左子树和右子树，并更新上下界return isBST(root.left, min, root.val) && isBST(root.right, root.val, max);}
}

二、96. 不同的二叉搜索树

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

示例 1：
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1
提示：

1 <= n <= 19

分析：

动态规划

class Solution {public int numTrees(int n) {// dp[i] 表示由 i 个节点组成且节点值从 1 到 i 的二叉搜索树的数量int[] dp = new int[n + 1];// 初始条件，空树也算一种情况，所以 dp[0] = 1dp[0] = 1;// 遍历每个节点数for (int i = 1; i <= n; i++) {// 遍历以当前节点为根节点的情况for (int j = 1; j <= i; j++) {// 左子树的节点数为 j-1，右子树的节点数为 i-jdp[i] += dp[j - 1] * dp[i - j];//组合数学里的乘法原理}}return dp[n];}
}

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

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

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左右子树也必须是二叉搜索树。

示例 1：
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2：
输入：root = [0,null,1]
输出：[1,null,1]
示例 3：
输入：root = [1,0,2]
输出：[3,3,2]
示例 4：
输入：root = [3,2,4,1]
输出：[7,9,4,10]
提示：

树中的节点数介于 0 和 104 之间。
每个节点的值介于 -104 和 104 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。

分析：

反序中序遍历，右中左
遍历过的节点都大于未遍历的节点，当前节点的新值即等于上一个遍历的节点的新值加上当前节点的旧值

class Solution {int sum = 0;public TreeNode convertBST(TreeNode root) {traverse(root);return root;}// 采用反序中序遍历，累加每个节点的值private void traverse(TreeNode root) {if (root == null) return;// 先遍历右子树traverse(root.right);// 更新当前节点的值为累加和sum += root.val;root.val = sum;// 再遍历左子树traverse(root.left);}
}