LeetCode算法题解| 669. 修剪二叉搜索树、108. 将有序数组转换为二叉搜索树、538. 把二叉搜索树转换为累加树

一、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，即当前树的所有节点值都在目标区间范围内，此时可以直接返回当前树的根节点。

以上四种情况排除之后，当前的情况是，根节点的值再目标区间范围内，但是最小值和最大值两个节点当中至少有一个不在目标区间范围内。

此时我们要分别向左右子树递归去修剪那些不合理的节点，然后再将当前的节点返回就可以啦！

代码如下：

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;//如果当前节点为空，直接返nullelse 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;}
}