669 修建二叉树
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
108 将有序数组转换为二叉搜索树
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def sub(l,r):
if l>r:
return None
mid=(l+r)//2
root=TreeNode(nums[mid])
root.left=sub(l,mid-1)
root.right=sub(mid+1,r)
return root
return sub(0,len(nums)-1)
538 把二叉搜索树转换为累加树
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def sub(root):
nonlocal total
if root:
sub(root.right)
total+=root.val
root.val=total
sub(root.left)
return root
total=0
sub(root)
return root
