今日任务：
1）669.修剪二叉搜索树
2）108.将有序数组转换为二叉搜索树
3）538.把二叉搜索树转换为累加树
669.修剪二叉搜索树
题目链接：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]
文章讲解：代码随想录 (programmercarl.com)
视频讲解：你修剪的方式不对，我来给你纠正一下！| LeetCode：669. 修剪二叉搜索树哔哩哔哩bilibili
思路：
这一题其实就是删除节点，与前一天打卡450.删除二叉搜索树中的节点类似
不一样的是，今天这题要删除的点不止一个，也可能没有
还有一点要格外注意，在450题中，我们是删除一个节点，其余都要保留，现在不一样了。
举个例子：
当遇到一个节点值小于下边界，那么这个节点的左子树可以全部删除了，省去了将左子树移到右子树上
且不能在此直接返回None，返回None就意味着将这个节点树整个删除了
但是搜索二叉树的右子树是大于跟节点的，所以这个节点右子树上的节点比当前节点大，可能存在符合要求的节点，不能删除
这个时候我们要继续遍历右子树，删除其不符合要求的节点后返回右子树根节点。
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right
class Solution:def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:# todo 1.判定所有情况的返回值# 如果节点为空，直接返回Noneif not root:return None# 如果节点小于下边界，则删除节点左子树，继续向节点右子树寻找if root.val < low:# 符合要要求的右子树节点返回right = self.trimBST(root.right,low,high)return right# 如果节点大于上边界，则删除节点右子树，继续向节点左子树寻找if root.val > high:# 符合要要求的左子树节点返回left = self.trimBST(root.left,low,high)return left# todo 2.根据不同的情况将返回值接收root.left = self.trimBST(root.left,low,high)root.right = self.trimBST(root.right,low,high)return root108.将有序数组转换为二叉搜索树
题目链接：108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）
给你一个整数数组 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] 都是高度平衡二叉搜索树。
文章讲解：代码随想录 (programmercarl.com)
视频讲解：构造平衡二叉搜索树！| LeetCode：108.将有序数组转换为二叉搜索树哔哩哔哩bilibili
思路：
这一题也与之前做过的题654.最大二叉树类似，之前是找出最大值，作为根节点，然后递归传入左右区间。
为什么说与之前的类似，如果是普通二叉树，那也就不类似了，一直插入叶子节点即可。
今天题目要求是平衡二叉树
平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
还有一点关键的，数组是有序的，所以我们只需要找到列表中间值作为根节点，以保证两边树的平均
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:# 可以不用判空，当nums为空的话，递归函数中left<right,返回空# if not nums:# returnreturn self.traveral(nums, 0, len(nums) - 1)def traveral(self, nums, left, right):if left > right:returnindex = (right + left) // 2node = TreeNode(nums[index])node.left = self.traveral(nums, left, index - 1)node.right = self.traveral(nums, index + 1, right)return node538.把二叉搜索树转换为累加树
题目链接：538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。示例 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 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。
文章讲解：代码随想录 (programmercarl.com)
视频讲解：普大喜奔！二叉树章节已全部更完啦！| LeetCode：538.把二叉搜索树转换为累加树哔哩哔哩bilibili
思路：
搜索二叉树采用中序遍历是有序的，而这题我们通过示例发现，它累加的方式正好是按中序遍历从大到小累加的
举个例子：
中序遍历：[0,1,2,3,4,5,6,7,8]
按上面顺序从大到小累加：[36,36,35,33,30,26,21,15,8]
8 = 8
15 = 8 + 7
21 = 8 + 7 + 6
所以比较简单的方法就是：逆中序遍历，累加重新赋予节点值即可
中序遍历是左中右，逆中序遍历便是右中左，定义累加和sum_，每次加上当前节点值并重新赋给当前节点
# Definition for a binary tree node.
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def __init__(self):self.sum_ = 0def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if not root:return root# 右self.convertBST(root.right)# 中self.sum_ += root.valroot.val = self.sum_# 左self.convertBST(root.left)return root另一个方法是采用双指针法，一个指针cur记录当前节点，一个指针pre记录上一个节点值
class Solution:def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:self.pre = 0self.traveral(root)return rootdef traveral(self, cur):if not cur:return# 右self.traveral(cur.right)# 中cur.val += self.preself.pre = cur.val# 左self.traveral(cur.left)
