东莞高端网站建设哪个好,php网站开发业务,设一个网站需要多少钱,做购物网站 需要手续669.修剪二叉搜索树
链接#xff1a;. - 力扣#xff08;LeetCode#xff09;
题目描述#xff1a; 给你二叉搜索树的根节点 root #xff0c;同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树#xff0c;使得所有节点的值在[low, high]中。修剪树 不应该 改变…669.修剪二叉搜索树
链接. - 力扣LeetCode
题目描述 给你二叉搜索树的根节点 root 同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即如果没有被移除原有的父代子代关系都应当保留)。 可以证明存在 唯一的答案 。 所以结果应当返回修剪好的二叉搜索树的新的根节点。注意根节点可能会根据给定的边界发生改变。 示例 1 输入root [1,0,2], low 1, high 2
输出[1,null,2]示例 2 输入root [3,0,4,null,2,null,null,1], low 1, high 3
输出[3,2,null,1]提示 树中节点数在范围 [1, 104] 内0 Node.val 104树中每个节点的值都是 唯一 的题目数据保证输入是一棵有效的二叉搜索树0 low high 104 思路 与删除二叉树节点的思路一样遍历二叉树当前节点如果小于我们需要的区间则删除该节点的左子树并且去遍历当前节点的右子树因为遍历的是二叉树搜索树因此右子树的值肯定是大于根节点的不确定右子树的所有元素都在我们需要的区间内因此需要去遍历当前节点如果大于我们需要的区间则删除该节点的右子树并且去遍历当前节点的左子树查看是否所有的节点都满足我们的区间 递归实现 1.确定函数参数和返回值函数的参数一个为要修剪的二叉树以及我们的区间范围返回值应该是修剪后的二叉树 2.确定终止条件如果当前节点为空则返回上一个节点否则查看当前节点的值是否满足我们的条件 3.确定单层递归逻辑遍历左右子树 代码实现 /*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
struct TreeNode* trimBST(struct TreeNode* root, int low, int high) {if(!root)return NULL;if(root-val low){struct TreeNode *tem root-right;//遍历该节点的右子树因为右子树比该节点大但是不一定都在范围内tem trimBST(root-right, low, high);free(root);return tem;}else if(root-val high){//遍历该节点的左子树因为左子树比该节点小但是不一定都在范围内struct TreeNode *tem root-left;tem trimBST(root-left, low, high);free(root);return tem;}root-left trimBST(root-left,low,high);root-right trimBST(root-right,low,high);return root;
} 108.将有序数组转换为二叉搜索树
链接. - 力扣LeetCode
题目描述 给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 平衡 二叉搜索树。 示例 1 输入nums [-10,-3,0,5,9]
输出[0,-3,9,-10,null,5]
解释[0,-10,5,null,-3,null,9] 也将被视为正确答案 示例 2 输入nums [1,3]
输出[3,1]
解释[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。提示 1 nums.length 104-104 nums[i] 104nums 按 严格递增 顺序排列 思路 与构建二叉树的思路一样对有序数组进行区间分割先找到数组中间元素的位置将其作为根节点因为数组是递增的且要构建搜索二叉树如何按照区间分割的思路来实现 递归实现 1.确定函数的参数和返回值函数参数应该为有序数组以及我们要分割的左右区间 2.确定递归终止条件如果我们数组的左右区间不符合正常情况则返回空 3.确定单层递归逻辑找到根节点位置进行区间的分割依次创建左右子树 代码实现 /*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
struct TreeNode *found(int *nums, int left, int right)
{if(left right)return NULL;struct TreeNode *node (struct TreeNode*)malloc(sizeof(struct TreeNode));int mid (left right) / 2;node-val nums[mid];node-left found(nums,left,mid-1);node-right found(nums,mid1,right);return node;
}struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {return found(nums,0,numsSize-1);
} 538.把二叉搜索树转化为累加树
链接. - 力扣LeetCode
题目描述 给出二叉 搜索 树的根节点该树的节点值各不相同请你将其转换为累加树Greater Sum Tree使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。 提醒一下二叉搜索树满足下列约束条件 节点的左子树仅包含键 小于 节点键的节点。节点的右子树仅包含键 大于 节点键的节点。左右子树也必须是二叉搜索树。 注意本题和 1038: . - 力扣LeetCode 相同 示例 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]提示 树中的节点数介于 0 和 104 之间。每个节点的值介于 -104 和 104 之间。树中的所有值 互不相同 。给定的树为二叉搜索树。 思路 根据二叉搜索树的性质我们可以知道中序遍历左中右得到的是一个递增的数组因为题目要求我们要得到累加树因此我们就要从右子树开始访问再依次累加因此我们的递归顺序就变为了右中左在实现累加操作时我们需要使用双指针的思路一个记录当前节点另一个记录前一个节点的值用来实现累加 递归实现 1.确定函数的参数和返回值因为我们只是要对树每个节点的值进行操作因此不需要返回值传入的参数应该是二叉树 2.确定递归的终止条件当我们二叉树遍历完成时递归终止 3.确定单层递归逻辑先去更新右子树再去处理根节点最后出来左子树 代码实现 /*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
int pre 0;
void fc(struct TreeNode *root)
{if(root NULL)return ;fc(root-right);root-val pre;pre root-val;fc(root-left);
}
struct TreeNode* convertBST(struct TreeNode* root) {pre 0;fc(root);return root;
}
