1.不同的二叉搜索树（96-中）
题目描述：给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例：
输入：n = 3
输出：5
思路：注意二叉排序树，因此如果选择 i 为根节点，那么左子树共有 i - 1 个节点，右子树共有 n - i 个节点，每种根节点对应的二叉树的数量肯定是两个子树情况的乘积，一共有n个这样的根节点。
- dp[i] 含义：i个节点组成的二叉搜索树数量
- 状态转移方程：dp[i] += dp[j - 1] * dp[i - j]
事实上，状态转移方程在数学上被称为卡塔兰数，便于计算的定义如下：
C0 = 1， Cn+1 = 2*Cn*(2*n + 1)/(n + 2)
代码：
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1; // 空树也是一种二叉搜索树
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
// 数学：卡特兰数
public int numTrees(int n) {
long ans = 1;
for (int i = 0; i < n; i++) {
ans = ans * 2 * (2 * i + 1) / (i + 2);
}
return (int)ans;
}
2.不同的二叉搜索树II（95-中）
题目描述：给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 ？返回满足题意的二叉搜索树。
示例：
输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
思路：二叉搜索树，对于任意一个节点大于左子树节点, 小于右子树节点。
- 主要思想为分治递归树，然后左右子树列表构建结果树。
- 注意：当n=0时，返回[], 但是F[0]]需要记录[[]]。
代码：
public List<TreeNode> generateTrees(int n) {
if (n < 1) {
return new LinkedList<TreeNode>();
}
return generateSubTrees(1, n);
}
private List<TreeNode> generateSubTrees(int s, int e) {
List<TreeNode> ret = new LinkedList<>();
if (s > e) {
//显然保证左子树或者右子树为空，正确构建树依赖下边左右子树列表的遍历，如果列表为空，那么循环不能进行。
ret.add(null);
return ret;
}
// 枚举所有可行的根节点
for (int i = s; i <= e; ++i) {
//1.分解：获取所有可行的左右子树集合
List<TreeNode> leftSubTrees = generateSubTrees(s, i - 1);
List<TreeNode> rightSubTrees = generateSubTrees(i + 1, e);
//2.合并：合并左右子树，需要创建leftSubTrees.size() * rightSubTrees.size()个根节点
for (TreeNode left : leftSubTrees) {
for (TreeNode right : rightSubTrees) {
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
ret.add(root);
}
}
}
return ret;
}
3.恢复二叉搜索树（99-难）
题目描述：给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
示例：
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
思路：显然利用中序序列的有序性，使用递归、迭代与morris（左子树为空和不为空两种情况）遍历解决，参考二叉树的中序遍历。注意交换的两种情况：
- 相邻两个数字交换（一组逆序对）
- 不相邻数字交换（两组逆序对）
代码：
// 递归解法
TreeNode first = null, second = null, pre = null;
public void recoverTree(TreeNode root) {
inOrder(root);
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
public void inOrder(TreeNode root) {
if (root == null) return;
inOrder(root.left);
if (pre != null && root.val < pre.val) {
if (first == null) {
first = pre;
second = root;
} else {
second = root;
}
}
pre = root;
inOrder(root.right);
}
// 迭代解法
TreeNode first = null, second = null, pre = null;
public void recoverTree(TreeNode root) {
inOrder(root);
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
public void inOrder(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (pre != null && root.val < pre.val) {
if (first == null) {
first = pre;
second = root;
} else {
second = root;
}
}
pre = root;
root = root.right;
}
}
// morris解法
public void recoverTree(TreeNode root) {
TreeNode first = null;
TreeNode second = null;
TreeNode cur = root;
TreeNode pre_new = null;
while (cur != null) {
// 情况 1
if (cur.left == null) {
/*******************************************************/
if (pre_new != null && cur.val < pre_new.val) {
if (first == null) {
first = pre_new;
second = cur;
} else {
second = cur;
}
}
pre_new = cur;
/*******************************************************/
cur = cur.right;
} else {
// 找左子树最右边的节点
TreeNode pre = cur.left;
while (pre.right != null && pre.right != cur) {
pre = pre.right;
}
// 情况 2.1（第一次到达左子树的最右节点，改变指针）
if (pre.right == null) {
pre.right = cur;
cur = cur.left;
}
// 情况 2.2（第二到达，恢复指针）
if (pre.right == cur) {
pre.right = null; // 这里可以恢复为 null
/*******************************************************/
if (pre_new != null && cur.val < pre_new.val) {
if (first == null) {
first = pre_new;
second = cur;
} else {
second = cur;
}
}
pre_new = cur;
/*******************************************************/
cur = cur.right;
}
}
}
int temp = first.val;
first.val = second.val;
second.val = temp;
}
4.验证二叉搜索树（98-中）
题目描述：验证一棵树是否为二叉搜索树：左子树节点都小于当前节点，右子树节点都大于当前节点，左右子树本身也是二叉搜索树。
示例：
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
思路：可以使用额外空间，可以通过二叉搜索树中序遍历的有序性进行判断，实现简单。
这里使用递归进行判断：
- 终止条件：root == null return true（空树也是二叉搜索树）
- 递归逻辑：当前节点与上一个节点值的大小关系
- 与二叉树的中序遍历相同：先左子树，当前节点，右子树
代码：
List<Integer> res = new ArrayList<>();
public boolean isValidBST(TreeNode root) {
inOrder(root);
for (int i = 1; i < res.size(); i++) {
if (res.get(i) <= res.get(i - 1)) {
return false;
}
}
return true;
}
private void inOrder(TreeNode root) {
if (root == null) return;
inOrder(root.left);
res.add(root.val);
inOrder(root.right);
}
//设置一个pre变量存上一个节点的值
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
if (!isValidBST(root.left)) {
return false;
}
//访问当前节点，当前节点小于或者等于中序遍历的上一个节点，不满足，否则继续
if (root.val <= pre) {
return false;
}
pre = root.val;
return isValidBST(root.right);
}
7.不同的二叉搜索树（96-中）
题目描述：给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例：
输入：n = 3
输出：5
思路：注意二叉排序树，因此如果选择 i 为根节点，那么左子树共有 i - 1 个节点，右子树共有 n - i 个节点，每种根节点对应的二叉树的数量肯定是两个子树情况的乘积，一共有n个这样的根节点。
- dp[i] 含义：i个节点组成的二叉搜索树数量
- 状态转移方程：dp[i] += dp[j - 1] * dp[i - j]
事实上，状态转移方程在数学上被称为卡塔兰数，便于计算的定义如下：
C0 = 1， Cn+1 = 2*Cn*(2*n + 1)/(n + 2)
代码：
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1; // 空树也是一种二叉搜索树
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
// 数学：卡特兰数
public int numTrees(int n) {
long ans = 1;
for (int i = 0; i < n; i++) {
ans = ans * 2 * (2 * i + 1) / (i + 2);
}
return (int)ans;
}
8.不同的二叉搜索树II（95-中）
题目描述：给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 ？返回满足题意的二叉搜索树。
示例：
输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
思路：二叉搜索树，对于任意一个节点大于左子树节点, 小于右子树节点。
- 主要思想为分治递归树，然后左右子树列表构建结果树。
- 注意：当n=0时，返回[], 但是F[0]]需要记录[[]]。
代码：
public List<TreeNode> generateTrees(int n) {
if (n < 1) {
return new LinkedList<TreeNode>();
}
return generateSubTrees(1, n);
}
private List<TreeNode> generateSubTrees(int s, int e) {
List<TreeNode> ret = new LinkedList<>();
if (s > e) {
//显然保证左子树或者右子树为空，正确构建树依赖下边左右子树列表的遍历，如果列表为空，那么循环不能进行。
ret.add(null);
return ret;
}
// 枚举所有可行的根节点
for (int i = s; i <= e; ++i) {
//1.分解：获取所有可行的左右子树集合
List<TreeNode> leftSubTrees = generateSubTrees(s, i - 1);
List<TreeNode> rightSubTrees = generateSubTrees(i + 1, e);
//2.合并：合并左右子树，需要创建leftSubTrees.size() * rightSubTrees.size()个根节点
for (TreeNode left : leftSubTrees) {
for (TreeNode right : rightSubTrees) {
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
ret.add(root);
}
}
}
return ret;
}
8.恢复二叉搜索树（99-难）
题目描述：给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
示例：
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
思路：显然利用中序序列的有序性，使用递归、迭代与morris（左子树为空和不为空两种情况）遍历解决，参考二叉树的中序遍历。注意交换的两种情况：
- 相邻两个数字交换（一组逆序对）
- 不相邻数字交换（两组逆序对）
代码：
// 递归解法
TreeNode first = null, second = null, pre = null;
public void recoverTree(TreeNode root) {
inOrder(root);
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
public void inOrder(TreeNode root) {
if (root == null) return;
inOrder(root.left);
if (pre != null && root.val < pre.val) {
if (first == null) {
first = pre;
second = root;
} else {
second = root;
}
}
pre = root;
inOrder(root.right);
}
// 迭代解法
TreeNode first = null, second = null, pre = null;
public void recoverTree(TreeNode root) {
inOrder(root);
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
public void inOrder(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (pre != null && root.val < pre.val) {
if (first == null) {
first = pre;
second = root;
} else {
second = root;
}
}
pre = root;
root = root.right;
}
}
// morris解法
public void recoverTree(TreeNode root) {
TreeNode first = null;
TreeNode second = null;
TreeNode cur = root;
TreeNode pre_new = null;
while (cur != null) {
// 情况 1
if (cur.left == null) {
/*******************************************************/
if (pre_new != null && cur.val < pre_new.val) {
if (first == null) {
first = pre_new;
second = cur;
} else {
second = cur;
}
}
pre_new = cur;
/*******************************************************/
cur = cur.right;
} else {
// 找左子树最右边的节点
TreeNode pre = cur.left;
while (pre.right != null && pre.right != cur) {
pre = pre.right;
}
// 情况 2.1（第一次到达左子树的最右节点，改变指针）
if (pre.right == null) {
pre.right = cur;
cur = cur.left;
}
// 情况 2.2（第二到达，恢复指针）
if (pre.right == cur) {
pre.right = null; // 这里可以恢复为 null
/*******************************************************/
if (pre_new != null && cur.val < pre_new.val) {
if (first == null) {
first = pre_new;
second = cur;
} else {
second = cur;
}
}
pre_new = cur;
/*******************************************************/
cur = cur.right;
}
}
}
int temp = first.val;
first.val = second.val;
second.val = temp;
}
8.验证二叉搜索树（98-中）
题目描述：验证一棵树是否为二叉搜索树：左子树节点都小于当前节点，右子树节点都大于当前节点，左右子树本身也是二叉搜索树。
示例：
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
思路：可以使用额外空间，可以通过二叉搜索树中序遍历的有序性进行判断，实现简单。
这里使用递归进行判断：
- 终止条件：root == null return true（空树也是二叉搜索树）
- 递归逻辑：当前节点与上一个节点值的大小关系
- 与二叉树的中序遍历相同：先左子树，当前节点，右子树
代码：
List<Integer> res = new ArrayList<>();
public boolean isValidBST(TreeNode root) {
inOrder(root);
for (int i = 1; i < res.size(); i++) {
if (res.get(i) <= res.get(i - 1)) {
return false;
}
}
return true;
}
private void inOrder(TreeNode root) {
if (root == null) return;
inOrder(root.left);
res.add(root.val);
inOrder(root.right);
}
//设置一个pre变量存上一个节点的值
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
if (!isValidBST(root.left)) {
return false;
}
//访问当前节点，当前节点小于或者等于中序遍历的上一个节点，不满足，否则继续
if (root.val <= pre) {
return false;
}
pre = root.val;
return isValidBST(root.right);
}
7.不同的二叉搜索树（96-中）
题目描述：给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例：
输入：n = 3
输出：5
思路：注意二叉排序树，因此如果选择 i 为根节点，那么左子树共有 i - 1 个节点，右子树共有 n - i 个节点，每种根节点对应的二叉树的数量肯定是两个子树情况的乘积，一共有n个这样的根节点。
- dp[i] 含义：i个节点组成的二叉搜索树数量
- 状态转移方程：dp[i] += dp[j - 1] * dp[i - j]
事实上，状态转移方程在数学上被称为卡塔兰数，便于计算的定义如下：
C0 = 1， Cn+1 = 2*Cn*(2*n + 1)/(n + 2)
代码：
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1; // 空树也是一种二叉搜索树
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
// 数学：卡特兰数
public int numTrees(int n) {
long ans = 1;
for (int i = 0; i < n; i++) {
ans = ans * 2 * (2 * i + 1) / (i + 2);
}
return (int)ans;
}
8.不同的二叉搜索树II（95-中）
题目描述：给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 ？返回满足题意的二叉搜索树。
示例：
输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
思路：二叉搜索树，对于任意一个节点大于左子树节点, 小于右子树节点。
- 主要思想为分治递归树，然后左右子树列表构建结果树。
- 注意：当n=0时，返回[], 但是F[0]]需要记录[[]]。
代码：
public List<TreeNode> generateTrees(int n) {
if (n < 1) {
return new LinkedList<TreeNode>();
}
return generateSubTrees(1, n);
}
private List<TreeNode> generateSubTrees(int s, int e) {
List<TreeNode> ret = new LinkedList<>();
if (s > e) {
//显然保证左子树或者右子树为空，正确构建树依赖下边左右子树列表的遍历，如果列表为空，那么循环不能进行。
ret.add(null);
return ret;
}
// 枚举所有可行的根节点
for (int i = s; i <= e; ++i) {
//1.分解：获取所有可行的左右子树集合
List<TreeNode> leftSubTrees = generateSubTrees(s, i - 1);
List<TreeNode> rightSubTrees = generateSubTrees(i + 1, e);
//2.合并：合并左右子树，需要创建leftSubTrees.size() * rightSubTrees.size()个根节点
for (TreeNode left : leftSubTrees) {
for (TreeNode right : rightSubTrees) {
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
ret.add(root);
}
}
}
return ret;
}
8.恢复二叉搜索树（99-难）
题目描述：给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
示例：
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
思路：显然利用中序序列的有序性，使用递归、迭代与morris（左子树为空和不为空两种情况）遍历解决，参考二叉树的中序遍历。注意交换的两种情况：
- 相邻两个数字交换（一组逆序对）
- 不相邻数字交换（两组逆序对）
代码：
// 递归解法
TreeNode first = null, second = null, pre = null;
public void recoverTree(TreeNode root) {
inOrder(root);
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
public void inOrder(TreeNode root) {
if (root == null) return;
inOrder(root.left);
if (pre != null && root.val < pre.val) {
if (first == null) {
first = pre;
second = root;
} else {
second = root;
}
}
pre = root;
inOrder(root.right);
}
// 迭代解法
TreeNode first = null, second = null, pre = null;
public void recoverTree(TreeNode root) {
inOrder(root);
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
public void inOrder(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (pre != null && root.val < pre.val) {
if (first == null) {
first = pre;
second = root;
} else {
second = root;
}
}
pre = root;
root = root.right;
}
}
// morris解法
public void recoverTree(TreeNode root) {
TreeNode first = null;
TreeNode second = null;
TreeNode cur = root;
TreeNode pre_new = null;
while (cur != null) {
// 情况 1
if (cur.left == null) {
/*******************************************************/
if (pre_new != null && cur.val < pre_new.val) {
if (first == null) {
first = pre_new;
second = cur;
} else {
second = cur;
}
}
pre_new = cur;
/*******************************************************/
cur = cur.right;
} else {
// 找左子树最右边的节点
TreeNode pre = cur.left;
while (pre.right != null && pre.right != cur) {
pre = pre.right;
}
// 情况 2.1（第一次到达左子树的最右节点，改变指针）
if (pre.right == null) {
pre.right = cur;
cur = cur.left;
}
// 情况 2.2（第二到达，恢复指针）
if (pre.right == cur) {
pre.right = null; // 这里可以恢复为 null
/*******************************************************/
if (pre_new != null && cur.val < pre_new.val) {
if (first == null) {
first = pre_new;
second = cur;
} else {
second = cur;
}
}
pre_new = cur;
/*******************************************************/
cur = cur.right;
}
}
}
int temp = first.val;
first.val = second.val;
second.val = temp;
}
8.验证二叉搜索树（98-中）
题目描述：验证一棵树是否为二叉搜索树：左子树节点都小于当前节点，右子树节点都大于当前节点，左右子树本身也是二叉搜索树。
示例：
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
思路：可以使用额外空间，可以通过二叉搜索树中序遍历的有序性进行判断，实现简单。
这里使用递归进行判断：
- 终止条件：root == null return true（空树也是二叉搜索树）
- 递归逻辑：当前节点与上一个节点值的大小关系
- 与二叉树的中序遍历相同：先左子树，当前节点，右子树
代码：
List<Integer> res = new ArrayList<>();
public boolean isValidBST(TreeNode root) {
inOrder(root);
for (int i = 1; i < res.size(); i++) {
if (res.get(i) <= res.get(i - 1)) {
return false;
}
}
return true;
}
private void inOrder(TreeNode root) {
if (root == null) return;
inOrder(root.left);
res.add(root.val);
inOrder(root.right);
}
//设置一个pre变量存上一个节点的值
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
if (!isValidBST(root.left)) {
return false;
}
//访问当前节点，当前节点小于或者等于中序遍历的上一个节点，不满足，否则继续
if (root.val <= pre) {
return false;
}
pre = root.val;
return isValidBST(root.right);
}
