669. 修剪二叉搜索树
树的修剪方式赋值。
1、递归法
class Solution:
def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
if root is None:
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
2、迭代法
class Solution:
def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
if root is None:
return None
# 先找到 root 的位置在 [low, high] 区间
while root and (root.val < low or root.val > high):
if root.val < low:
root = root.right
else:
root = root.left
cur = root
# 处理小于 low 的部分
while cur:
while cur.left and cur.left.val < low:
cur.left = cur.left.right # 赋值剪枝
cur = cur.left
cur = root
while cur:
while cur.right and cur.right.val > high:
cur.right = cur.right.left # 赋值剪枝
cur = cur.right
return root
108.将有序数组转换为二叉搜索树
1、递归法
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
return self.traversal(nums, 0, len(nums) - 1)
def traversal(self, nums, left, right):
if left > right:
return None
mid = left + (right - left) // 2
root = TreeNode(nums[mid])
root.left = self.traversal(nums, left, mid-1)
root.right = self.traversal(nums, mid+1, right)
return root
538.把二叉搜索树转换为累加树
1、迭代法
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root is None:
return
cur = root
stack = []
pre = 0 # 记录上一个节点的值
while cur or stack:
# 右
if cur:
stack.append(cur)
cur = cur.right
else:
# 中
cur = stack.pop()
if pre:
cur.val += pre.val
pre = cur
# 左
cur = cur.left
return root
2、递归
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
self.pre = 0 # 记录前一个节点
self.traversal(root)
return root
def traversal(self, root):
if root is None:
return
self.traversal(root.right) # 右
# 中
if self.pre:
root.val += self.pre
self.pre = root.val
self.traversal(root.left) # 左