一、LeetCode 669 修建二叉搜索树
题目链接：669.修建二叉搜索树
https://leetcode.cn/problems/trim-a-binary-search-tree/description/
思路：递归三部曲-定参数、返回值-定终止条件-定单层递归逻辑
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(root == null){return root;}if(root.val < low){//剪枝操作，root的左子树肯定都在区间之外，所以直接返回root的右子树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;}
}
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/二、LeetCode 108 将有序数组转换为二叉搜索树
题目链接：108.将有序数组转换为二叉搜索树https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/
思路：分割数组 左闭右闭 递归造树
class Solution {public TreeNode sortedArrayToBST(int[] nums) {int n = nums.length;int left = 0;int right = n-1;return travel(nums,0,n-1);}public TreeNode travel(int[] nums, int left, int right){if(left > right){return null;}int index = left + (right-left)/2;TreeNode root = new TreeNode(nums[index]);//左闭右闭，中间节点已入树root.left = travel(nums, left, index-1);root.right = travel(nums, index+1, right);return root;}
}
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/三、LeetCode 538 把二叉搜索树转换为累加树
题目链接：538.把二叉搜索树转换为累加树https://leetcode.cn/problems/convert-bst-to-greater-tree/
思路：二叉搜索树的中序遍历结果是顺序数组->反中序遍历然后顺序累加可得结果
class Solution {//记录前一个节点的值int pre = 0;public TreeNode convertBST(TreeNode root) {travel(root);return root;}public void travel(TreeNode root){//按右中左遍历if(root == null){return;}travel(root.right);//累加求和 保存累加值pre += root.val;root.val = pre;travel(root.left);}
}
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/四、小结
恨残照，犹有一竿红、怪人催去早 \*AVA*/ $^*^$
