前言

代码随想录算法训练营day23

一、Leetcode 669. 修剪二叉搜索树

1.题目

给你二叉搜索树的根节点 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. 树中节点数在范围 [1, 104] 内
2. 0 <= Node.val <= 104
3. 树中每个节点的值都是 唯一 的
4. 题目数据保证输入是一棵有效的二叉搜索树
5. 0 <= low <= high <= 104

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/trim-a-binary-search-tree

2.解题思路

方法一：递归

对根结点 rootroot 进行深度优先遍历。对于当前访问的结点，如果结点为空结点，直接返回空结点；如果结点的值小于 lowlow，那么说明该结点及它的左子树都不符合要求，我们返回对它的右结点进行修剪后的结果；如果结点的值大于 highhigh，那么说明该结点及它的右子树都不符合要求，我们返回对它的左子树进行修剪后的结果；如果结点的值位于区间 [low,high][low,high]，我们将结点的左结点设为对它的左子树修剪后的结果，右结点设为对它的右子树进行修剪后的结果。

3.代码实现

```java class Solution { public TreeNode trimBST(TreeNode root, int low, int high) { if (root == null) { return null; } if (root.val < low) { return trimBST(root.right, low, high); } else if (root.val > high) { return trimBST(root.left, low, high); } else { root.left = trimBST(root.left, low, high); root.right = trimBST(root.right, low, high); return root; } } }
```

二、Leetcode 108.将有序数组转换为二叉搜索树

1.题目

给你一个整数数组 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. 1 <= nums.length <= 104
2. -104 <= nums[i] <= 104
3. nums 按 严格递增 顺序排列

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree

2.解题思路

方法一：中序遍历，总是选择中间位置左边的数字作为根节点

选择中间位置左边的数字作为根节点，则根节点的下标为 mid=(left+right)/2mid=(left+right)/2，此处的除法为整数除法。

3.代码实现

```java class Solution { public TreeNode sortedArrayToBST(int[] nums) { return helper(nums, 0, nums.length - 1); }

1. public TreeNode helper(int[] nums, int left, int right) {
2. if (left > right) {
3. return null;
4.     }
5. 
6. // 总是选择中间位置左边的数字作为根节点
7.     int mid = (left + right) / 2;
8. 
9.     TreeNode root = new TreeNode(nums[mid]);
10.     root.left = helper(nums, left, mid - 1);
11.     root.right = helper(nums, mid + 1, right);
12. return root;
13. }

}

```

三、Leetcode 538.把二叉搜索树转换为累加树

1.题目

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树(Greater Sum Tree)，使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

1. 节点的左子树仅包含键 小于 节点键的节点。
2. 节点的右子树仅包含键 大于 节点键的节点。
3. 左右子树也必须是二叉搜索树。

示例 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]

提示：

1. 树中的节点数介于 0 和 104 之间。
2. 每个节点的值介于 -104 和 104 之间。
3. 树中的所有值 互不相同 。
4. 给定的树为二叉搜索树。

2.解题思路

方法一：反序中序遍历

本题中要求我们将每个节点的值修改为原来的节点值加上所有大于它的节点值之和。这样我们只需要反序中序遍历该二叉搜索树，记录过程中的节点值之和，并不断更新当前遍历到的节点的节点值，即可得到题目要求的累加树。

3.代码实现

```java class Solution { int sum = 0;

1. public TreeNode convertBST(TreeNode root) {
2. if (root != null) {
3.         convertBST(root.right);
4. sum += root.val;
5.         root.val = sum;
6.         convertBST(root.left);
7.     }
8. return root;
9. }

}

```