Day23 二叉树09
669. 修剪二叉搜索树
题目链接：669. 修剪二叉搜索树 - 力扣（LeetCode）
思路：节点值不在区间式，返回的不是子节点，而是递归调度,而且根据二叉搜索树特征，该节点小于key则所有左子树都小于key，右子树同理。
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.将有序数组转换为二叉搜索树
题目链接：108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）
思路：从中间节点开始
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return sortedArrayToBST1(nums,0,nums.length);
}
public TreeNode sortedArrayToBST1(int[] nums, int left, int right){
if(left>=right) return null;
if(right - left == 1) return new TreeNode(nums[left]);
int mid = left +(right - left) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = sortedArrayToBST1(nums,left,mid);
root.right = sortedArrayToBST1(nums,mid+1,right);
return root;
}
}538.把二叉搜索树转换为累加树
题目链接：538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）
思路：双指针法，需要额外调度函数
class Solution {
int pre;
public TreeNode convertBST(TreeNode root) {
pre = 0;
convertBST1(root);
return root;
}
public void convertBST1(TreeNode root){
if(root == null) return;
convertBST1(root.right);
pre = pre + root.val;
root.val = pre;
convertBST1(root.left);
return;
}
}