参考文档：代码随想录
108.将有序数组转换为二叉搜索树
力扣题目链接(opens new window)
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
-
使用什么来转换?
-
当时的问题是:如何将有序数组转换为二叉搜索树，具体是使用什么转换？
-
将有序数组转换为二叉搜索树
-
数组是有序的平衡二叉树，可选用中间元素作为根节点
-
数组左边的元素都小于中间元素，可用于构建左子树；数组右边的元素都大于中间元素，可用于构建右子树。然后对左右子数组分别递归地应用相同的方法，最终构建出完整的二叉搜索树。
-
递归法代码解析
class Solution {
private:// 辅助函数，用于递归地将有序数组转换为二叉搜索树TreeNode* traversal(vector<int>& nums, int left, int right) {// 递归终止条件：如果左边界大于右边界，说明当前区间为空，返回空指针if (left > right) return nullptr;// 计算中间位置的索引，使用这种方式避免整数溢出int mid = left + ((right - left) / 2);// 创建一个新的节点，节点的值为中间位置的元素TreeNode* root = new TreeNode(nums[mid]);// 递归构建左子树，左子树的区间为 [left, mid - 1]root->left = traversal(nums, left, mid - 1);// 递归构建右子树，右子树的区间为 [mid + 1, right]root->right = traversal(nums, mid + 1, right);// 返回当前构建好的子树的根节点return root;}
public:// 主函数，将有序数组转换为二叉搜索树TreeNode* sortedArrayToBST(vector<int>& nums) {// 调用辅助函数，从数组的起始位置（0）到结束位置（nums.size() - 1）开始构建TreeNode* root = traversal(nums, 0, nums.size() - 1);// 返回构建好的二叉搜索树的根节点return root;}
};
看完答案后的解析
root -> left = traversal(nums, left, mid - 1); 这是涉及到了二分法的什么部分吗？
- 用到了二分法的思想。在
traversal函数中 数组的中间元素作为 子数组的根节点。数组 分成左右两个部分，一个是左子树，一个是右子树。
538.把二叉搜索树转换为累加树
力扣题目链接(opens new window)
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。
示例 1：
- 输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
- 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2：
- 输入：root = [0,null,1]
- 输出：[1,null,1]
示例 3：
- 输入：root = [1,0,2]
- 输出：[3,3,2]
示例 4：
- 输入：root = [3,2,4,1]
- 输出：[7,9,4,10]
思路分析
节点的相加原则是什么？
- 所有大于它的节点以及它本身相加，而它又是一颗二叉搜索树，所以中序便利可以直接秒了
代码实现：
class Solution {
private:int pre = 0; // 记录前一个节点的数值void traversal(TreeNode* cur) { // 右中左遍历if (cur == NULL) return;traversal(cur->right);cur->val += pre; pre = cur->val;traversal(cur->left);}
public:TreeNode* convertBST(TreeNode* root) {pre = 0;traversal(root);return root;}
};
669. 修剪二叉搜索树
力扣题目链接(opens new window)
给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。
思路分析
- 什么叫合适区间的节点?寻找符合区间[low, high]的节点
- 符合区间
[low, high]的节点，指的是节点的值val满足以下条件的节点 low <= node.val <= high- 例如，给定区间
[3, 7]：- 节点值为
3、4、5、6、7的节点都属于合适区间的节点。 - 节点值为
2的节点就不属于这个区间，因为2 < 3。 - 节点值为
8的节点也不属于这个区间，因为8 > 7。
- 节点值为
- 例如，给定区间
- 符合区间
- 剪枝的范围是什么意思
- “剪枝的范围” 是指节点保留，那些节点需要从树移除一个节点的数值
- low 表示区间下限，high表示区间上限。
代码解析
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if (root == nullptr ) return nullptr;if (root->val < low) {TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点return right;}if (root->val > high) {TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点return left;}root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子return root;}
};
难点主要是要理解题目的意思
今日用时3h
如果觉得对你有帮助的话
麻烦点一个免费的赞👍