当前位置:   article > 正文

代码随想录算法训练营day23 | 669. 修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树

代码随想录算法训练营day23 | 669. 修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树

669. 修剪二叉搜索树

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. # def __init__(self, val=0, left=None, right=None):
  4. # self.val = val
  5. # self.left = left
  6. # self.right = right
  7. class Solution:
  8. def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
  9. '''
  10. 确认递归函数参数以及返回值:返回更新后剪枝后的当前root节点
  11. '''
  12. # Base Case
  13. if not root: return None
  14. # 单层递归逻辑
  15. if root.val < low:
  16. # 若当前root节点小于左界:只考虑其右子树,用于替代更新后的其本身,抛弃其左子树整体
  17. return self.trimBST(root.right, low, high)
  18. if high < root.val:
  19. # 若当前root节点大于右界:只考虑其左子树,用于替代更新后的其本身,抛弃其右子树整体
  20. return self.trimBST(root.left, low, high)
  21. if low <= root.val <= high:
  22. root.left = self.trimBST(root.left, low, high)
  23. root.right = self.trimBST(root.right, low, high)
  24. # 返回更新后的剪枝过的当前节点root
  25. return root

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

在构造二叉树的时候尽量不要重新定义左右区间数组,而是用下标来操作原数组。

  1. class Solution:
  2. def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
  3. '''
  4. 构造二叉树:重点是选取数组最中间元素为分割点,左侧是递归左区间;右侧是递归右区间
  5. 必然是平衡树
  6. 左闭右闭区间
  7. '''
  8. # 返回根节点
  9. root = self.traversal(nums, 0, len(nums)-1)
  10. return root
  11. def traversal(self, nums: List[int], left: int, right: int) -> TreeNode:
  12. # Base Case
  13. if left > right:
  14. return None
  15. # 确定左右界的中心,防越界
  16. mid = left + (right - left) // 2
  17. # 构建根节点
  18. mid_root = TreeNode(nums[mid])
  19. # 构建以左右界的中心为分割点的左右子树
  20. mid_root.left = self.traversal(nums, left, mid-1)
  21. mid_root.right = self.traversal(nums, mid+1, right)
  22. # 返回由被传入的左右界定义的某子树的根节点
  23. return mid_root

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

把它想成是有序数组一直做累加就行,还是双指针的操作思路~

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. # def __init__(self, val=0, left=None, right=None):
  4. # self.val = val
  5. # self.left = left
  6. # self.right = right
  7. class Solution:
  8. def __init__(self):
  9. self.pre = TreeNode()
  10. def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
  11. '''
  12. 倒序累加替换:
  13. [2, 5, 13] -> [[2]+[1]+[0], [2]+[1], [2]] -> [20, 18, 13]
  14. '''
  15. self.traversal(root)
  16. return root
  17. def traversal(self, root: TreeNode) -> None:
  18. # 因为要遍历整棵树,所以递归函数不需要返回值
  19. # Base Case
  20. if not root:
  21. return None
  22. # 单层递归逻辑:中序遍历的反译 - 右中左
  23. self.traversal(root.right) # 右
  24. # 中节点:用当前root的值加上pre的值
  25. root.val += self.pre.val # 中
  26. self.pre = root
  27. self.traversal(root.left) # 左
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/1021235
推荐阅读
相关标签
  

闽ICP备14008679号