企业官网建设流程全解析

怎样看一个网站的浏览量,重庆皇华建设集团有限公司网站,自建站工具,国内餐饮类网站欣赏669. 修剪二叉搜索树 目标#xff1a; 给一棵 BST 和区间 [low, high]#xff0c;删除所有值不在区间内的节点#xff0c;并返回修剪后的 新 root。 核心思路#xff08;先记住这 3 句#xff09; BST 区间 剪整棵子树 root.val low → 整个左子树都不要root.val 给一棵 BST 和区间[low, high]删除所有值不在区间内的节点并返回修剪后的新 root。核心思路先记住这 3 句BST 区间 剪整棵子树root.val low→ 整个左子树都不要root.val high→ 整个右子树都不要否则 → 保留当前节点递归修剪左右为什么可以“整棵剪”BST 性质若root.val low 左子树所有值 root.val low→ 全不合法若root.val high 右子树所有值 root.val high→ 全不合法定义 trimBST(node)返回「以 node 为根修剪完成后的子树的新根」 过程-若 node 为空returnNone这棵子树不存在-若 node.vallow 当前节点不合法returntrimBST(node.right)-若 node.valhigh 当前节点不合法returntrimBST(node.left)-否则 当前节点合法 左子树的新根trimBST(node.left)右子树的新根trimBST(node.right)将新左右子树接回 nodereturnnode代码# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:deftrimBST(self,root:Optional[TreeNode],low:int,high:int)-Optional[TreeNode]:# 【base case】# 走到空节点说明这条路径已经没有节点了# 返回 None 表示这棵子树修剪后不存在ifnotroot:returnNone# 【情况 1当前节点太小】# root.val low# - 当前节点不合法不能出现在最终结果中# - 根据 BST 性质左子树一定也都 low可以整体丢掉# - 这棵子树新的 root 只能来自右子树# 所以直接返回「右子树修剪后的新根」ifroot.vallow:returnself.trimBST(root.right,low,high)# 【情况 2当前节点太大】# root.val high# - 当前节点不合法# - 右子树一定也都 high可以整体丢掉# - 新的 root 只能来自左子树ifroot.valhigh:returnself.trimBST(root.left,low,high)# 【情况 3当前节点合法】# root.val 在 [low, high] 内# - 当前节点可以保留# - 但左右子树是否保留要等递归返回结果# 这里不会立刻 return而是“接住”下一层的返回值root.leftself.trimBST(root.left,low,high)root.rightself.trimBST(root.right,low,high)# 左右子树都已经修剪完成# 当前 root 仍然合法作为这一层子树的新根返回returnroot指标复杂度说明时间复杂度O(h)只沿 BST 高度剪枝空间复杂度O(h)递归调用栈108.将有序数组转换为二叉搜索树目标给一个升序数组nums把它转换成一棵高度平衡的 BST并返回root。核心思路每一次递归都做同一件事 选当前区间的中点作为 root保证左右子树高度接近 左半边数组 → 左子树 右半边数组 → 右子树 return 当前构造好的 root代码情况一区间递归helper(l, r)# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:defsortedArrayToBST(self,nums:List[int])-Optional[TreeNode]:# helper(l, r) 的语义# 用 nums[l..r]闭区间构造一棵 BST# 并返回这棵子树构造完成后的「根节点」defhelper(l,r):# 【base case】# 当区间为空l r说明这段数组构不成子树# 返回 None表示“这棵子树不存在”iflr:returnNone# 1️⃣ 选择当前区间的中点作为根节点# 因为数组有序选中点可以保证左右子树高度接近mid(lr)//2nodeTreeNode(nums[mid])# 2️⃣ 构造左子树# 左子树使用区间 [l, mid-1]# helper 返回的是左子树构造完成后的新根node.lefthelper(l,mid-1)# 3️⃣ 构造右子树# 右子树使用区间 [mid1, r]# 注意这里必须是 r而不是 r1# 因为我们始终使用的是闭区间 [l, r]node.righthelper(mid1,r)# 4️⃣ 左右子树都已经构造完成# 当前 node 就是这段区间对应子树的新根# return 给上一层递归使用returnnode# 从整个数组区间 [0, n-1] 开始构造returnhelper(0,len(nums)-1)指标复杂度说明时间复杂度O(n)每个数组元素只被用来创建一个节点空间复杂度O(log n)递归深度等于平衡 BST 的高度情况二切片递归nums[:mid]# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:defsortedArrayToBST(self,nums:List[int])-Optional[TreeNode]:# 递归函数的“语义”# sortedArrayToBST(nums) 返回# 用当前 nums这个子数组构造出的 BST 的根节点# 【base case】# 当数组为空说明这段数据构不成子树# 返回 None表示“这棵子树不存在”ifnotnums:returnNone# 1️⃣ 选择当前数组的中点作为根节点# 因为 nums 是有序的选中点可以保证左右子树高度接近midlen(nums)//2rootTreeNode(nums[mid])# 2️⃣ 用中点左边的子数组递归构造左子树# 递归返回的是左子树构造完成后的新 rootroot.leftself.sortedArrayToBST(nums[:mid])# 3️⃣ 用中点右边的子数组递归构造右子树# 返回的是右子树构造完成后的新 rootroot.rightself.sortedArrayToBST(nums[mid1:])# 4️⃣ 左右子树都已经构造完成# 当前 root 作为“这棵子树的新根”返回给上一层returnroot指标复杂度说明时间复杂度O(n log n)每一层递归都会拷贝数组切片空间复杂度O(n)所有递归层产生的切片数组占用内存538.把二叉搜索树转换为累加树目标给一棵 BST把每个节点的值改成原值 所有比它大的节点值之和返回修改后的 root。核心思路BST 的中序遍历是升序 想从「大到小」累加 就用反向中序遍历右 → 根 → 左在遍历过程中维护一个running sum累计和。BST 性质左子树 根 右子树普通中序左 → 根 → 右小 → 大反向中序右 → 根 → 左大 → 小 我们要先看到“更大的值”才能加给当前节点。totalrunning sum的含义total表示在反向中序遍历中 已经访问过的所有节点值之和所有比当前节点大的节点之和一开始total 0每访问一个节点先把当前节点值加到total再用total更新当前节点的值代码classSolution:defconvertBST(self,root):# total 的含义非常重要# 在反向中序遍历过程中# 已经访问过的所有节点值之和# 也就是“当前节点右边更大的所有节点之和”total0defreverse_inorder(node):nonlocaltotalifnotnode:return# 1️⃣ 先访问右子树# 因为 BST 中右子树的值都比当前节点大# 所以先处理右边才能先累加“更大的值”reverse_inorder(node.right)# 2️⃣ 处理当前节点# 走到这里时# total 已经等于# 所有「比 node.val 大的节点值之和」## 现在我们把当前节点也加进去totalnode.val# 更新当前节点的值# 新值 原值 所有比它大的值node.valtotal# 3️⃣ 再访问左子树# 左子树里的值都比当前节点小# 但它们要加的是# 包含当前节点在内的 totalreverse_inorder(node.left)reverse_inorder(root)returnroot指标复杂度说明时间复杂度O(n)每个节点在反向中序遍历中访问一次空间复杂度O(h)递归调用栈深度等于树高