代码随想录算法训练营第二十三天| 669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树

669. 修剪二叉搜索树

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

解题思路：如果当前结点小于所给区间，那该节点及其左子树肯定不符合条件，返回其右子树作为上一结点子树；反之亦然。

C：
 

struct TreeNode* trimBST(struct 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;
}

java：
 

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.将有序数组转换为二叉搜索树

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

解题思路：用折半查找法，取中间值为根节点

C:

typedef struct TreeNode TreeNode;
struct TreeNode* traversal(int* nums, int left, int right) {if (left > right) return NULL;int mid = left + ((right - left) / 2);TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));root->val=nums[mid];root->left = traversal(nums, left, mid - 1);root->right = traversal(nums, mid + 1, right);return root;
}
struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {TreeNode* root = traversal(nums, 0, numsSize - 1);return root;
}

java：

class Solution {public TreeNode sortedArrayToBST(int[] nums) {return sortedArrayToBST(nums, 0, nums.length);}public TreeNode sortedArrayToBST(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 = sortedArrayToBST(nums, left, mid);root.right = sortedArrayToBST(nums, mid + 1, right);return root;}
}

538.把二叉搜索树转换为累加树

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

解题思路：逆中序遍历

java：

class Solution {TreeNode pre=null;public TreeNode convertBST(TreeNode root) {if(root==null) return null;convertBST(root.right);if(pre!=null) root.val+=pre.val;pre=root;convertBST(root.left);return root;}
}