网站域名所有权 查询,网站正在建设中模板下载,用户体验最好的网站,产品管理系统669. 修剪二叉搜索树 思路#xff1a;利用二叉搜索树的性质#xff0c;对于每个节点#xff0c;判断其是否在区间内#xff1a; 如果节点值 low#xff0c;则此节点和其左子树都不在范围内如果节点值 high#xff0c;则此节点和其右子树都不在范围内如果 low 利用二叉搜索树的性质对于每个节点判断其是否在区间内 如果节点值 low则此节点和其左子树都不在范围内如果节点值 high则此节点和其右子树都不在范围内如果 low 节点值 high则保留此节点但需要递归修建其左右子树 class Solution:def trimBST(self, root: Optional[TreeNode], low: int, high: int) - Optional[TreeNode]:if not root:return None# 如果节点小于low返回右子树修剪的结果if root.val low:return self.trimBST(root.right, low, high)# 如果节点大于high返回左子树修剪的结果elif root.val high:return self.trimBST(root.left, low, high)# 如果节点在区间内递归修建左右子树else: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 helper(left, right):if left right:return Nonemid (left right) // 2root TreeNode(nums[mid])root.left helper(left, mid - 1)root.right helper(mid 1, right)return rootreturn helper(0, len(nums)-1)
538.把二叉搜索树转换为累加树 什么是累加树 指在二叉搜索树BST的基础上进行转换得到的一种特殊形式的树。在累加树中每个节点的值被替换为原始二叉搜索树中所有大于该节点值的节点值之和加上该节点自身的值。 思路我们从最大值开始累加因此遍历顺序是元素从大到小。我们可以使用反向中序遍历来实现右中左。 class Solution:def convertBST(self, root: Optional[TreeNode]) - Optional[TreeNode]:self.sum 0def traverse(node):if not node:return# 反向中序遍历右 - 根 - 左traverse(node.right)self.sum node.valnode.val self.sumtraverse(node.left)traverse(root)return root
