网站开发范围文昌网站建设 myvodo

网站开发范围,文昌网站建设 myvodo,淘宝网站的订单管理怎么做,android获取wordpress数据库连接1.递归思想#xff1a; 首先弄清楚递和归 递就是将一个大问题分解为多个相同的子问题 在计算机真正实现的时候#xff0c;计算机会一个个将你递的问题#xff0c;放进栈中#xff0c;这也是为什么递归 的时候空间复杂度是O#xff08;n#xff09;#xff0c;计算机背…1.递归思想首先弄清楚递和归递就是将一个大问题分解为多个相同的子问题在计算机真正实现的时候计算机会一个个将你递的问题放进栈中这也是为什么递归 的时候空间复杂度是On计算机背后实际上创建了一个深度为n 的栈当前在处理那一层栈都有对应把一个复杂的大问题按照相同的逻辑拆解成规模更小的子问题直到子问题小到能直接解决触达边界条件。比如 if root None 就是已经递到最底下了完成全部的递了核心作用避免递归无限拆解栈溢出同时为 “归” 提供初始结果。现在开始规而归就是执行非边界条件做逻辑计算机行为栈是 “先进后出” 的最后压入的子问题先出栈计算结果向上传递给上一层问题。class Solution: def maxDepth(self, root: TreeNode) - int: # 边界条件递的终止 if root is None: return 0 # 递触发子问题等待子问题的归结果 left_depth self.maxDepth(root.left) right_depth self.maxDepth(root.right) # 归显性拆分两步更易理解 # 第一步合并子问题结果找左右子树的最大深度 max_child_depth max(left_depth, right_depth) # 第二步计算当前层深度子树最大深度 当前节点返回向上归 current_depth max_child_depth 1 return current_depth还有前序遍历的思路# class Solution: # def maxDepth(self, root:Optional[TreeNode])-int : # ans 0 # def qianxubianli(node,cnt): # if root None: # return 0 # nonlocal ans # cnt 1 # ans max(ans, cnt) # qianxubianli(root.left,cnt) # qianxubianli(root.right,cnt) # qianxubianli(root,0) # return ans2.相同的树递归检查子树分别递归判断p和q的左子树、右子树是否相同把结果存在两个变量里。a self.isSameTree(p.left,q.left)b self.isSameTree(p.right,q.right)return a and b在此基础上加上边界条件if p None or q Noneclass Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) - bool: #首先核心如何比较两个树就是比较两个树的左子树比较两个数的右子树 if p None or q None: #情况一p或q只是有一个空节点 return p q # if p.val ! q.val: #情况二pq不空但不相等剪枝操作没必要后续再递归 # return False a self.isSameTree(p.left, q.left) b self.isSameTree(p.right, q.right) return a and b and p.val q.val3.对称树思路核心虽然紧接着上个题很容易想到构造一个isSameTree但还是要总结一下拆分成子问题就是比较两个树的节点比较A树的左节点和B树的右节点是否一样但题目只给了root一个根节点那就把它拆开然后就有了整体的思路了class Solution: def isSymmetric(self, root: Optional[TreeNode]) - bool: def isSameTree(node1,node2): if node1 None or node2 None: return node1 node2 a isSameTree(node1.left,node2.right) b isSameTree(node1.right,node2.left) return a and b and node1.valnode2.val return isSameTree(root.left,root.right)还可以进一步优化两个空树也是对称树所以加上if root is None核心价值优先处理空树本质是「鲁棒性保障」避免崩溃用例 1root []空树用例 2root [1]单节点树左 / 右子树都是空用例 3root [1,2,2]非空树但子节点包含空。如果没处理rootNone用例 1 直接报错用例 2 也要走递归处理 “两个空节点”执行耗时自然被拉高。相同树的核心是「对比两棵独立的树」入口直接传两棵树的根节点对称树的核心是「把一棵树拆成左右两半对比这两半是否镜像」入口只传一棵树的根节点必须先拆成 left/right 再对比。这也就是为何对称树要额外加一个判断初始给的root是否为空咯4.平衡树子问题不是比较左右子树的高度吗那不是应该分开求左右子树高度你的理解有个关键偏差“判断平衡” 的子问题不是 “先分开求完左右高度再比较”而是 “在求高度的过程中同步判断平衡” ——后者自底向上比前者自顶向下分开求效率高一个量级而 max(left_height, right_height) 1 正是 “求高度 判平衡” 的核心衔接点-1是 “带不平衡标记的数值”要理解为什么求树高 判平衡的递归函数用get_height(node)而非get_height(node, depth)核心是这个函数的核心目标是「自底向上计算节点高度」高度由子树推导而来而非依赖外部传入的「depth深度」而 depth 是「自顶向下标记层级」的变量和 “高度计算” 的逻辑无关。def get_height(node): if not node: return 0 # 求左高度的同时若左子树不平衡直接返回-1剪枝 left_h get_height(node.left) if left_h -1: return -1 # 求右高度的同时若右子树不平衡直接返回-1剪枝 right_h get_height(node.right) if right_h -1: return -1 # 求完左右高度后立刻判当前节点的平衡 if abs(left_h - right_h) 1: return -1 # 平衡则返回当前节点高度供父节点判断 else: return max(left_h, right_h) 1流程递归左判断子节点是否传上来了-1递归右判断子节点是否传上来了-1子节点为什么会传上来-1 if abs(left_h - right_h) 1:返回节点高度这一步和求树高度是一样的一句话右视图一、先明确递归的核心逻辑你提到的关键结论递归解决树的问题的本质边界条件定义 “递归什么时候停”通常是空节点最小问题只关注 “当前节点该做什么”不用管子树的细节子树等价性假设递归调用能正确处理 “左 / 右子树”返回子树的有效结果只需基于子树结果处理当前节点即可。1. 边界条件定义递归的终止规则最小的 “无意义问题”边界条件的意义空节点是递归中 “最小的无效问题”—— 空节点没有值也没有子树无需处理直接返回即可这是递归的 “底线”保证递归不会无限执行也避免了对 “无意义节点” 的无效计算。2. 最小问题只关注 “当前节点该做什么”不用管子树最小问题的定义对于任意一个非空节点它只需要判断 “自己是否是当前层的第一个被访问节点”—— 这是当前节点的 “唯一职责”不用管左 / 右子树长什么样、怎么遍历3. 子树等价性假设递归能处理子树只需复用其逻辑我们还原右视图的完整解题思考过程就能更清晰看到 “先第三步、后第二步” 的逻辑问题目标找每一层的最右侧节点核心难点如何保证 “先访问最右侧节点”→ 想到 “右优先 DFS”第三步的思路衍生问题如何标记 “每一层第一个被访问的节点”→ 想到 “depth 和 len (ans) 匹配”第二步的思路代码落地把思路转化为 “先判断标记第二步、再递归遍历第三步”符合递归自顶向下的执行逻辑。