前言

本文隶属于专栏《LeetCode 刷题汇总》，该专栏为笔者原创，引用请注明来源，不足和错误之处请在评论区帮忙指出，谢谢！

本专栏目录结构请见LeetCode 刷题汇总

正文

幕布

幕布链接

96. 不同的二叉搜索树

题解

官方题解​

动态规划

class Solution {public int numTrees(int n) {int[] G = new int[n + 1];G[0] = G[1] = 1;for (int i = 2; i <= n; i++) {for (int j = 1; j <= i; j++) {G[i] += G[j - 1] * G[i - j];}}return G[n];}
}

数学，卡特兰数

class Solution {public int numTrees(int n) {// 提示：我们在这里需要用 long 类型防止计算过程中的溢出long C = 1;for (int i = 0; i < n; ++i) {C = C * 2 * (2 * i + 1) / (i + 2);}return (int) C;}
}

97. 交错字符串

题解

类似路径问题，找准状态方程快速求解​

路径问题

class Solution {public boolean isInterleave(String s1, String s2, String s3) {int m = s1.length(), n = s2.length();if (s3.length() != m + n) return false;// 动态规划，dp[i,j]表示s1前i字符能与s2前j字符组成s3前i+j个字符；boolean[][] dp = new boolean[m+1][n+1];dp[0][0] = true;for (int i = 1; i <= m && s1.charAt(i-1) == s3.charAt(i-1); i++) dp[i][0] = true; // 不相符直接终止for (int j = 1; j <= n && s2.charAt(j-1) == s3.charAt(j-1); j++) dp[0][j] = true; // 不相符直接终止for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {dp[i][j] = (dp[i - 1][j] && s3.charAt(i + j - 1) == s1.charAt(i - 1))|| (dp[i][j - 1] && s3.charAt(i + j - 1) == s2.charAt(j - 1));}}return dp[m][n];}
}

98. 验证二叉搜索树

题解

官方题解​

递归 + long pre

class Solution {long pre = Long.MIN_VALUE; // 记录上一个节点的值，初始值为Long的最小值public boolean isValidBST(TreeNode root) {return inorder(root);}// 中序遍历private boolean inorder(TreeNode node) {if(node == null) return true;boolean l = inorder(node.left);if(node.val <= pre) return false;pre = node.val;return l && inorder(node.right);}
}

栈迭代+long pre

class Solution {private boolean flag = true;private long pre = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root == null){return true;}helper(root);return flag;}private void helper(TreeNode root){Stack<TreeNode> stack = new Stack<>();while(root != null || !stack.isEmpty()){while(root != null){stack.push(root);root = root.left;}root = stack.pop();if(root.val <= pre){flag = false;break;}pre = root.val;root = root.right;}}
}

99. 恢复二叉搜索树

题解

官方题解​

显式中序遍历+数组+递归

class Solution {public void recoverTree(TreeNode root) {List<Integer> nums = new ArrayList<Integer>();inorder(root, nums);int[] swapped = findTwoSwapped(nums);recover(root, 2, swapped[0], swapped[1]);}public void inorder(TreeNode root, List<Integer> nums) {if (root == null) {return;}inorder(root.left, nums);nums.add(root.val);inorder(root.right, nums);}public int[] findTwoSwapped(List<Integer> nums) {int n = nums.size();int index1 = -1, index2 = -1;for (int i = 0; i < n - 1; ++i) {if (nums.get(i + 1) < nums.get(i)) {index2 = i + 1;if (index1 == -1) {index1 = i;} else {break;}}}int x = nums.get(index1), y = nums.get(index2);return new int[]{x, y};}public void recover(TreeNode root, int count, int x, int y) {if (root != null) {if (root.val == x || root.val == y) {root.val = root.val == x ? y : x;if (--count == 0) {return;}}recover(root.left, count, x, y);recover(root.right, count, x, y);}}
}

隐式中序遍历+栈，x/y/prev

class Solution {public void recoverTree(TreeNode root) {Deque<TreeNode> stack = new ArrayDeque<>();TreeNode x = null, y = null, prev = null;while (!stack.isEmpty() || root != null) {while (root != null) {stack.push(root);root = root.left;}root = stack.pop();if (prev != null && root.val < prev.val) {y = root;if (x == null) {x = prev;} else {break;}}prev = root;root = root.right;}swap(x, y);}public void swap(TreeNode x, TreeNode y) {int tmp = x.val;x.val = y.val;y.val = tmp;}
}

Morris 遍历算法

class Solution {public void recoverTree(TreeNode root) {TreeNode x = null, y = null, pred = null, predecessor = null;while (root != null) {if (root.left != null) {// predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止predecessor = root.left;while (predecessor.right != null && predecessor.right != root) {predecessor = predecessor.right;}// 让 predecessor 的右指针指向 root，继续遍历左子树if (predecessor.right == null) {predecessor.right = root;root = root.left;}// 说明左子树已经访问完了，我们需要断开链接else {if (pred != null && root.val < pred.val) {y = root;if (x == null) {x = pred;}}pred = root;predecessor.right = null;root = root.right;}}// 如果没有左孩子，则直接访问右孩子else {if (pred != null && root.val < pred.val) {y = root;if (x == null) {x = pred;}}pred = root;root = root.right;}}swap(x, y);}public void swap(TreeNode x, TreeNode y) {int tmp = x.val;x.val = y.val;y.val = tmp;}
}

100. 相同的树

题解

官方题解​

递归

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if (p == null && q == null) {return true;} else if (p == null || q == null) {return false;} else if (p.val != q.val) {return false;} else {return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}}
}