669. 修剪二叉搜索树
669. 修剪二叉搜索树 - 力扣（LeetCode）
本题主要分为3种情况，如果root.val<low，那么去右子树修剪，此时不能直接返回右子树，因为右子树可能有不符合规则的，如果root.val>high，同理去左子树修剪，如果在low和high内，那么保留root，并赋予root的左右子树
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if (root == null) return null;
if (root.val < low) {
// 不保留root，返回修剪后的右节点
return trimBST(root.right, low, high);
} else if (root.val > high) {
return trimBST(root.left, low, high);
} else {
// 保留root
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
}
}
108.将有序数组转换为二叉搜索树
108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）
本题可以分为左闭右开和左闭右闭，将中间的值作为根节点，左边作为左子树，右边作为右子树
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
TreeNode root = sortedArrayToBST(nums, 0, nums.length-1);
return root;
}
public TreeNode sortedArrayToBST(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int middle = (left + right) / 2;
TreeNode node = new TreeNode(nums[middle]);
node.left = sortedArrayToBST(nums, left, middle-1);
node.right = sortedArrayToBST(nums, middle+1, right);
return node;
}
}
538.把二叉搜索树转换为累加树
538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）
将节点的值换成大于等于该值的节点的和，按照右中左的中序遍历的方法，用sum记录总和
class Solution {
int sum;
public TreeNode convertBST(TreeNode root) {
sum = 0;
sumTreeNode(root);
return root;
}
public void sumTreeNode(TreeNode root) {
if (root == null) {
return;
}
sumTreeNode(root.right);
sum += root.val;
root.val = sum;
sumTreeNode(root.left);
}
}
