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

目录

一、669. 修剪二叉搜索树

二、108. 将有序数组转换为二叉搜索树

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

一、669. 修剪二叉搜索树

题目链接：力扣

文章讲解：代码随想录

视频讲解： 你修剪的方式不对，我来给你纠正一下！| LeetCode：669. 修剪二叉搜索树

题目：

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:/*TreeNode* trimBST(TreeNode* root, int low, int high) {//没有很好的利用搜索树左小右大的特性if (!root) return root;root->left = trimBST(root->left, low, high);root->right = trimBST(root->right, low, high);if (root->val < low || root->val > high){if (!root->left) return root->right;else if (!root->right) return root->left;else{TreeNode* new_node = root->left;while(new_node->right) new_node = new_node->right;new_node->right = root->right;root = root->left;}}return root;//递归法if(!root) 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;}*///递归法TreeNode* trimBST(TreeNode* root, int low, int high) {if (!root) return nullptr;//将根节点移到合理范围内while (root && (root->val < low || root->val > high))if (root->val < low) root = root->right;else root = root->left;TreeNode *node = root;// 处理左子树，处理左子树的过程中，合理继续向左（node的右子树一定合理)，不合理就向右（node的左子树一定不合理）if(!root) return NULL;for (;node->left;) if(node->left->val < low) node->left = node->left->right;else node = node->left;// 处理右子树，处理右子树的过程中，合理继续向右（node的左子树一定合理)，不合理就向左（node的右子树一定不合理）for (node = root;node->right;)if (node->right->val > high)node->right = node->right->left;else node = node->right;return root;}
};

时间复杂度: O(n)                                        空间复杂度: O(1)

⏲：9:13

总结：1.考虑二叉搜索树特性，如果root结点不符合条件，那么左右子树有一个必不符合条件，另一个可能存在不符合条件的结点。

           2.不考虑特性，则要删除root结点，则需要参考二叉树删除结点的方法。

二、108. 将有序数组转换为二叉搜索树

题目链接：力扣

文章讲解：代码随想录

视频讲解：构造平衡二叉搜索树！| LeetCode：108.将有序数组转换为二叉搜索树

题目：给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* bulid(vector<int>& nums, int begin, int end){if(begin > end) return NULL;int mid = ((end - begin)>>1) + begin;TreeNode* root = new TreeNode(nums[mid]);root->left = bulid(nums, begin, mid-1);root->right = bulid(nums, mid+1, end);return root;}TreeNode* sortedArrayToBST(vector<int>& nums) {return bulid(nums, 0, nums.size()-1);}
};

时间复杂度: O(n)                                        空间复杂度: O(logn)

⏲：4:11

总结：1.根据数组构造二叉树，考虑分治来递归。二叉搜索树要求顺序，则左子树在root左边，右子树在root右边。平衡二叉树要求左右结点数相近，则root结点选取mid。

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

题目链接：力扣

文章讲解：代码随想录

视频讲解：普大喜奔！二叉树章节已全部更完啦！| LeetCode：538.把二叉搜索树转换为累加树

题目：给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。

代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* pre;TreeNode* convertBST(TreeNode* root) {if (!root) return NULL;convertBST(root->right);if (pre) root->val += pre->val;pre = root;convertBST(root->left);return root;}
};

时间复杂度: O(n)                                        空间复杂度O(n)

⏲：2:21

总结：1、观察知，所谓累计所有比自己大的结点的值在二叉搜索树(中序遍历可变为有序数组)中，可表现为自身的值加上上一个结点的值（已经累加过）即可。故采用反中序遍历即从大到小进行累加。

         2、迭代法可通过构造线索二叉树，将空间复杂度压缩为O(1)。