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); }
