669. 修剪二叉搜索树
思路：二叉搜索树有序，若当前结点值大于high，递归左子树，小于low，递归右子树。后要将下一层处理完左子树的结果赋给root->left，处理完右子树的结果赋给root->right
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.将有序数组转换为二叉搜索树
思路：
- 数组的长度用nums.length记录
- 取中点，分左右（左闭右闭）
- 注意避免越界
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
TreeNode root = travelsal(nums, 0, nums.length - 1);
return root;
}
public TreeNode travelsal(int[] nums, int left, int right) {
if (left > right)
return null;
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = travelsal(nums, left, mid - 1);
root.right = travelsal(nums, mid + 1, right);
return root;
}
}
538.把二叉搜索树转换为累加树
思路：
- pre的位置，需要设置成全局，否则作用域为局部的话，每次调用都会创建新的pre值为0
class Solution {
int pre = 0;
public TreeNode convertBST(TreeNode root) {
travelsal(root);
return root;
}
public void travelsal(TreeNode root) {
if (root == null)
return;
travelsal(root.right);
root.val += pre;
pre = root.val;
travelsal(root.left);
}
}
