给你一个整数 n ,请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
示例 1:
输入:n = 3
输出:[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
示例 2:
输入:n = 1 输出:[[1]]
public List<TreeNode> generateTrees(int n) {
if (n == 0) {
return new LinkedList<>();
}
return generateTrees(1, n);
}
private List<TreeNode> generateTrees(int start, int end) {
List<TreeNode> allTrees = new LinkedList<>();
if (start > end) {
allTrees.add(null);
return allTrees;
}
for (int i = start; i <= end; i++) {
// 获得所有可行的左子树集合
List<TreeNode> leftTrees = generateTrees(start, i - 1);
// 获得所有可行的右子树集合
List<TreeNode> rightTrees = generateTrees(i + 1, end);
for (TreeNode left : leftTrees) {
for (TreeNode right : rightTrees) {
TreeNode cur = new TreeNode(i);
cur.left = left;
cur.right = right;
allTrees.add(cur);
}
}
}
return allTrees;
}
给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
示例 1:
输入:n = 3 输出:5
示例 2:
输入:n = 1 输出:1
public int numTrees(int n) {
int [] g = new int[n + 1];
g[0] = 1;
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];
}
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:root = [2,1,3] 输出:true
示例 2:
输入:root = [5,1,4,null,null,3,6] 输出:false 解释:根节点的值是 5 ,但是右子节点的值是 4 。
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean isValidBST(TreeNode node, long lower, long upper) {
if (node == null) {
return true;
}
if (node.val <= lower || node.val >= upper) {
return false;
}
return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
}
给你二叉搜索树的根节点 root ,该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下,恢复这棵树 。
示例 1:
输入:root = [1,3,null,null,2] 输出:[3,1,null,null,2] 解释:3 不能是 1 的左孩子,因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2:
输入:root = [3,1,4,null,null,2] 输出:[2,1,4,null,null,3] 解释:2 不能在 3 的右子树中,因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
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.right, count, x, y);
recover(root.left, count, x, y);
}
}
给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例 1:
输入:p = [1,2,3], q = [1,2,3] 输出:true
示例 2:
输入:p = [1,2], q = [1,null,2] 输出:false
示例 3:
输入:p = [1,2,1], q = [1,1,2] 输出:false
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);
}
}