网站建设文翻译工作,网站建设需要注意哪些细节,女教师遭网课入侵视频大全集,阿里云主机建网站669.修剪二叉搜索树 根据给定的最小边界 left 和最大边界 right 修剪二叉搜索树#xff0c;保留值在 left ~ right 的节点#xff0c;删除不满足此条件的节点。修剪树不应该改变保留在树中的元素的相对结构#xff0c;即父子关系。 设 cur 为当前访问的二叉树节点#xff0…669.修剪二叉搜索树 根据给定的最小边界 left 和最大边界 right 修剪二叉搜索树保留值在 left ~ right 的节点删除不满足此条件的节点。修剪树不应该改变保留在树中的元素的相对结构即父子关系。 设 cur 为当前访问的二叉树节点可分为以下情况 1cur-val 小于 left当前节点应该被删除但是根据二叉搜索树的性质当前节点的右子树可能满足 cur-val 大于 left即不能删除以当前节点为根的整棵二叉树应该仅删除当前节点还需要遍历其右子树 2cur- val 大于 right当前节点应该被删除根据二叉搜索树的性质当前节点的左子树可能满足 cur-val 小于 right还需要遍历其左子树 3cur-val 满足给定区间此时继续向下遍历即可。
class Solution {
public:TreeNode* trimBST(TreeNode *root, int low, int high) {if (root nullptr) return nullptr;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.将有序数组转换为二叉搜索树 二叉搜索树要求其右子树的值大于根节点左子树的值小于根节点左右子树均满足这个条件。因此根节点是中间的值所以从有序数组的中间一分为二左边初始化为左子树右边初始化为右子树。
class Solution {
private:TreeNode* traversal(vectorint nums, int left, int right) {if (left right) return nullptr;int mid left ((right - left) / 2);TreeNode *node new TreeNode(nums[mid]);node-left traversal(nums, left, mid - 1);node-right traversal(nums, mid 1, right);return node;}public:TreeNode* sortedArrayToBST(vectorint nums) {TreeNode *root traversal(nums, 0, nums.size() - 1);return root; 538.将二叉搜索树转换为累加树
class Solution {
private:int pre 0;void traversal(TreeNode *cur) {if (cur nullptr) return;traversal(cur-right);cur-val pre;pre cur-val;traversal(cur-left);}public:TreeNode* convertBST(TreeNode *root) {pre 0;traversal(root);return root;}
};
相关文章：
