前言
本文隶属于专栏《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);
}
}
}