day23 打卡669. 修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树
669. 修剪二叉搜索树
1.迭代法
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if (root == null) return null;
if (root.val<low) {
return trimBST(root.right, low, high);
}
if (root.val>high) {
return trimBST(root.left, low, high);
}
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
}
108.将有序数组转换为二叉搜索树
1.递归法
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return sortedArrayToBST(nums, 0 , nums.length);
}
public TreeNode sortedArrayToBST(int[] nums, int start, int end) {
if (start>=end) return null;
if (end-start==1) return new TreeNode(nums[start]);
int mid = start + (end-start)/2;
TreeNode cur = new TreeNode(nums[mid]);
cur.left = sortedArrayToBST(nums, start, mid);
cur.right = sortedArrayToBST(nums, mid+1, end);
return cur;
}
}
538.把二叉搜索树转换为累加树
1.递归法
class Solution {
int sum = 0;
public TreeNode convertBST(TreeNode root) {
if (root==null) return null;
convertBST1(root);
return root;
}
public void convertBST1(TreeNode cur) {
if (cur == null) return;
// 右
convertBST(cur.right);
// 中
sum += cur.val;
cur.val = sum;
// 左
convertBST(cur.left);
}
}