梧州网站设计公司,网站运营seo实训总结,做跨境电商开店流程,做淘宝客网站用什么程序好669. 修剪二叉搜索树
力扣链接 给定一个二叉搜索树#xff0c;同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树#xff0c;使得所有节点的值在[L, R]中 (RL)
思路
如果当前节点元素小于low#xff0c;递归右子树#xff0c;返回符合条件的头节点 如果当前节点元…669. 修剪二叉搜索树
力扣链接 给定一个二叉搜索树同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树使得所有节点的值在[L, R]中 (RL)
思路
如果当前节点元素小于low递归右子树返回符合条件的头节点 如果当前节点元素大于high递归左子树返回复合条件的头节点 最后root.left接入符合条件的左孩子root.right接入符合条件的右孩子
class Solution:def trimBST(self, root: Optional[TreeNode], low: int, high: int) - Optional[TreeNode]:if root None:return rootif root.val low:right self.trimBST(root.right, low, high)return rightif root.val high:left self.trimBST(root.left, low, high)return leftroot.left self.trimBST(root.left, low, high)root.right self.trimBST(root.right, low, high)return root108.将有序数组转换为二叉搜索树
力扣链接 给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 平衡二叉搜索树左右子树深度差不超过1
思路
对于有序数组中间元素为根节点右边的元素放右孩子左边的元素放左孩子。
class Solution:def sortedArrayToBST(self, nums: List[int]) - Optional[TreeNode]:root self.traversal(nums, 0, len(nums)-1)return rootdef traversal(self, nums, left, right):if left right:return Nonemid (left right)//2root TreeNode(nums[mid])root.left self.traversal(nums, left, mid-1)root.right self.traversal(nums, mid1, right)return root538.把二叉搜索树转换为累加树
力扣链接 给出二叉 搜索 树的根节点该树的节点值各不相同请你将其转换为累加树Greater Sum Tree使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
思路
保存上一节点的数值用中序遍历反着的构建
class Solution:def convertBST(self, root: Optional[TreeNode]) - Optional[TreeNode]:self.pre 0 # 记录前一个节点的值self.traversal(root)return rootdef traversal(self, node):if node is None:return # 中序遍历倒序# 右self.traversal(node.right)# 中node.val self.preself.pre node.val# 左self.traversal(node.left)
