题目简介
669. 修剪二叉搜索树
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
108.将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
538.把二叉搜索树转换为累加树
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同
初见思路
- 用递归思想，当前节点小于low，删除后的树由它的右子树构建；当前节点大于high，那么新树只能由它的左子树构建。如果当前节点值在范围内，那么向下递归，我们有：
class Solution:
def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
if not root:
return None
if root.val < low:
return self.trimBST(root.right, low, high)
if root.val > high:
return self.trimBST(root.left, low, high)
root.left = self.trimBST(root.left, low, high)
root.right = self.trimBST(root.right, low, high)
return root
- 两个注意点： 数组升序，构建BST。结合二分查找的思想，不难发现对于每个子区间中点左边的节点都小于它，右边都大于它，就能写出：
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
if len(nums) == 1:
return TreeNode(nums[0])
return self.buildTree(nums, 0, len(nums) - 1)
def buildTree(self,nums:List[int],start:int,end:int) -> Optional[TreeNode]:
if start == end:
return TreeNode(nums[start])
if start > end:
return None
mid = start + (end - start) // 2
root = TreeNode(nums[mid])
root.left = self.buildTree(nums, start, mid-1)
root.right = self.buildTree(nums, mid+1, end)
return root
- 结合BST特性，左小右大，所以我们累加的时候每次都是从右向左进行累加，每次累加后记录当前节点为前一节点即可。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return root
self.pre = 0
self.traversal(root)
return root
def traversal(self,root)->None:
if not root:
return
self.traversal(root.right)
root.val += self.pre
self.pre = root.val
self.traversal(root.left)
复盘思路
https://programmercarl.com/0669.%E4%BF%AE%E5%89%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
