一、LeetCode 669. 修剪二叉搜索树
题目链接:669. 修剪二叉搜索树
题目描述:
给你二叉搜索树的根节点 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
算法分析:
利用递归和回溯思想。
写出两个方法分别找出当前树的最大直节点以及最小值节点。
public TreeNode Max(TreeNode root) {//找出二叉搜索树的最大值节点
if(root == null) return root;
else if(root.right != null) return Max(root.right);
else return root;
}
public TreeNode Min(TreeNode root) {//找到二叉搜索树的最小值节点
if(root == null) return root;
else if(root.left != null) return Min(root.left);
else return root;
}
在递归函数中,
如果当前节点为空,直接返回null。
如果当前节点的值大于目标区间的最大值high,说明当前节点以及右子树的所有节点值都不在区间范围内,剪去当前节点以及右子树。
如果当前节点的值小于目标区间的最小值low,说明当前节点以及左子树的所有节点值都不在目标区间范围内,减去当前节点以及左子树。
如果当前树的最大直小于目标区间最大值high,并且最小值大于目标区间最小值low,即当前树的所有节点值都在目标区间范围内,此时可以直接返回当前树的根节点。
以上四种情况排除之后,当前的情况是,根节点的值再目标区间范围内,但是最小值和最大值两个节点当中至少有一个不在目标区间范围内。
此时我们要分别向左右子树递归去修剪那些不合理的节点,然后再将当前的节点返回就可以啦!
代码如下:文章来源:https://www.toymoban.com/news/detail-740299.html
class Solution {
public TreeNode Max(TreeNode root) {//找出二叉搜索树的最大值节点
if(root == null) return root;
else if(root.right != null) return Max(root.right);
else return root;
}
public TreeNode Min(TreeNode root) {//找到二叉搜索树的最小值节点
if(root == null) return root;
else if(root.left != null) return Min(root.left);
else return root;
}
public TreeNode trimBST(TreeNode root, int low, int high) {
if(root == null) return null;//如果当前节点为空,直接返null
else if(root.val > high) return trimBST(root.left, low, high);//如果当前节点的值大于high,那么说明右子树的全部节点值都不在目标区间内,向左递归去寻找合理的节点
else if(root.val < low) return trimBST(root.right, low, high);//反之如果当前节点的值小于low,说明当前节点及左子树全部节点的值都不在目标区间内,向右递归去寻找合理的节点
else if(Max(root).val <= high && Min(root).val >= low) return root;//如果当前树的最大值小于等于high并且最小值大于等于low,即当前树在目标区间范围内,则可以直接返回当前树的根节点
else {//到这儿的情况是,根节点的值在目标区间范围内,儿最大值和最小值至少有一个不在区间范围
root.left = trimBST(root.left, low, high);//向左子树递归去修剪不合理的节点,再返回左子树的根节点
root.right = trimBST(root.right, low, high);//向右递归去修剪右子树的不合理节点,在返回根节点
return root;//此时左右子树都修剪完了,返回当前节点
}
}
}
二、 LeetCode108. 将有序数组转换为二叉搜索树
题目链接:108. 将有序数组转换为二叉搜索树
题目描述:
给你一个整数数组 nums
,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例 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] <= 104
-
nums
按 严格递增 顺序排列
提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
-
nums
按 严格递增 顺序排列
算法分析
根据二叉搜索树的性质(每个节点的做左右子树高度差不超过一),题目给我们的是一个有序的数组。
那么我们每次只去要找道数组的中间元素作为树的根节点,然后将数组从中间分割成两个数组,左数组用来创建左子树,右数组用来创建右子树。
然后向左右数组依次递归下去,最后返回根节点即可。
代码如下:
class Solution {
public TreeNode BuildTree(int[] nums, int left, int right) {//区间利用左闭右开原则
if(left >= right) return null;//如果左区间大于等于有区间返回空节点
if(right - left == 1) return new TreeNode(nums[left]);//如果区间内只有一个元素,将当前元素创建成节点后返回
else {//区间内有多个元素时
int mid = left + (right - left) / 2;//找到这段区间内的中间元素
TreeNode node = new TreeNode(nums[mid]);//将中间元素创建成节点,以该节点为树的根节点
node.left = BuildTree(nums, left, mid);//利用递归创建左子树
node.right = BuildTree(nums, mid + 1, right);//利用递归创建右子树
return node;//返回当前书的根节点
}
}
public TreeNode sortedArrayToBST(int[] nums) {
return BuildTree(nums, 0, nums.length);
}
}
三、538. 把二叉搜索树转换为累加树
题目链接:538. 把二叉搜索树转换为累加树
题目描述:
给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(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
之间。 - 树中的所有值 互不相同 。
- 给定的树为二叉搜索树。
算法分析:
利用右中左序遍历,当前节点的是值加等于前一个节点的值。
代码如下:
class Solution {
int pre = 0;//记录前一个节点的值
public void midTravel(TreeNode cur) {//右中左序遍历
if(cur == null) return;
midTravel(cur.right);
cur.val += pre;
pre = cur.val;
midTravel(cur.left);
}
public TreeNode convertBST(TreeNode root) {
midTravel(root);
return root;
}
}
总结
修剪二叉搜索树、构造二叉搜索树、累加树。文章来源地址https://www.toymoban.com/news/detail-740299.html
到了这里,关于LeetCode算法题解| 669. 修剪二叉搜索树、108. 将有序数组转换为二叉搜索树、538. 把二叉搜索树转换为累加树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!