js网站开发工具,家具网站开发环境与工具,自己如何申请域名,设计一个logo目录
一、669. 修剪二叉搜索树
二、108. 将有序数组转换为二叉搜索树
三、538. 把二叉搜索树转换为累加树 一、669. 修剪二叉搜索树
题目链接#xff1a;力扣
文章讲解#xff1a;代码随想录
视频讲解#xff1a; 你修剪的方式不对#xff0c;我来给你纠正一下#…目录
一、669. 修剪二叉搜索树
二、108. 将有序数组转换为二叉搜索树
三、538. 把二叉搜索树转换为累加树 一、669. 修剪二叉搜索树
题目链接力扣
文章讲解代码随想录
视频讲解 你修剪的方式不对我来给你纠正一下| LeetCode669. 修剪二叉搜索树
题目
给你二叉搜索树的根节点 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. 将有序数组转换为二叉搜索树
题目链接力扣
文章讲解代码随想录
视频讲解构造平衡二叉搜索树| LeetCode108.将有序数组转换为二叉搜索树
题目给你一个整数数组 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(vectorint 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, mid1, end);return root;}TreeNode* sortedArrayToBST(vectorint nums) {return bulid(nums, 0, nums.size()-1);}
};
时间复杂度: O(n) 空间复杂度: O(logn)
⏲4:11
总结1.根据数组构造二叉树考虑分治来递归。二叉搜索树要求顺序则左子树在root左边右子树在root右边。平衡二叉树要求左右结点数相近则root结点选取mid。 三、538. 把二叉搜索树转换为累加树
题目链接力扣
文章讲解代码随想录
视频讲解普大喜奔二叉树章节已全部更完啦| LeetCode538.把二叉搜索树转换为累加树
题目给出二叉 搜索 树的根节点该树的节点值各不相同请你将其转换为累加树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)。
