赞
踩
- # 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 trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
- '''
- 确认递归函数参数以及返回值:返回更新后剪枝后的当前root节点
- '''
- # Base Case
- if not root: return None
-
- # 单层递归逻辑
- if root.val < low:
- # 若当前root节点小于左界:只考虑其右子树,用于替代更新后的其本身,抛弃其左子树整体
- return self.trimBST(root.right, low, high)
-
- if high < root.val:
- # 若当前root节点大于右界:只考虑其左子树,用于替代更新后的其本身,抛弃其右子树整体
- return self.trimBST(root.left, low, high)
-
- if low <= root.val <= high:
- root.left = self.trimBST(root.left, low, high)
- root.right = self.trimBST(root.right, low, high)
- # 返回更新后的剪枝过的当前节点root
- return root

在构造二叉树的时候尽量不要重新定义左右区间数组,而是用下标来操作原数组。
- class Solution:
- def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
- '''
- 构造二叉树:重点是选取数组最中间元素为分割点,左侧是递归左区间;右侧是递归右区间
- 必然是平衡树
- 左闭右闭区间
- '''
- # 返回根节点
- root = self.traversal(nums, 0, len(nums)-1)
- return root
-
- def traversal(self, nums: List[int], left: int, right: int) -> TreeNode:
- # Base Case
- if left > right:
- return None
-
- # 确定左右界的中心,防越界
- mid = left + (right - left) // 2
- # 构建根节点
- mid_root = TreeNode(nums[mid])
- # 构建以左右界的中心为分割点的左右子树
- mid_root.left = self.traversal(nums, left, mid-1)
- mid_root.right = self.traversal(nums, mid+1, right)
-
- # 返回由被传入的左右界定义的某子树的根节点
- return mid_root

把它想成是有序数组一直做累加就行,还是双指针的操作思路~
- # 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 __init__(self):
- self.pre = TreeNode()
-
- def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
- '''
- 倒序累加替换:
- [2, 5, 13] -> [[2]+[1]+[0], [2]+[1], [2]] -> [20, 18, 13]
- '''
- self.traversal(root)
- return root
-
- def traversal(self, root: TreeNode) -> None:
- # 因为要遍历整棵树,所以递归函数不需要返回值
- # Base Case
- if not root:
- return None
- # 单层递归逻辑:中序遍历的反译 - 右中左
- self.traversal(root.right) # 右
-
- # 中节点:用当前root的值加上pre的值
- root.val += self.pre.val # 中
- self.pre = root
-
- self.traversal(root.left) # 左

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。