本机电脑怎么做网站良品铺子网络营销策划方案

本机电脑怎么做网站,良品铺子网络营销策划方案,体育视频网站建设,北京网站搭建服务二叉树的遍历是树形结构中最基础的操作。所谓的**“前序遍历”**#xff0c;其实是指“根节点”相对于左右子树的访问顺序。 1. 记住口诀#xff1a;根 - 左 - 右 前序遍历#xff08;Pre-order Traversal#xff09;的逻辑非常固定#xff1a; 首先访问 根节点…二叉树的遍历是树形结构中最基础的操作。所谓的**“前序遍历”**其实是指“根节点”相对于左右子树的访问顺序。1. 记住口诀根 - 左 - 右前序遍历Pre-order Traversal的逻辑非常固定首先访问根节点 (Root)。然后递归地访问左子树 (Left)。最后递归地访问右子树 (Right)。2. 解法一递归法最直观递归是最符合树定义的方法因为树本身就是递归定义的。classSolution:defpreorderTraversal(self,root:Optional[TreeNode])-List[int]:res[]defdfs(node):ifnotnode:return# 1. 根先记录当前节点的值res.append(node.val)# 2. 左递归遍历左子树dfs(node.left)# 3. 右递归遍历右子树dfs(node.right)dfs(root)returnres3. 解法二迭代法利用栈 Stack在面试中面试官经常会问“如果不让你用递归你怎么实现”这时我们需要模拟递归的过程。递归本质上是利用了系统的调用栈所以我们可以手动维护一个栈 (Stack)。关键点栈是“后进先出”的。为了保证“先左后右”的访问顺序我们在压栈时要先压右子树再压左子树。classSolution:defpreorderTraversal(self,root:Optional[TreeNode])-List[int]:ifnotroot:return[]stack[root]res[]whilestack:# 弹出栈顶节点当前的“根”nodestack.pop()res.append(node.val)# 先把右孩子放进去后出ifnode.right:stack.append(node.right)# 再把左孩子放进去先出ifnode.left:stack.append(node.left)returnres4. 总结与对比前序遍历根 - 左 - 右中序遍历左 - 根 - 右145 题后序遍历左 - 右 - 根94 题为什么迭代法里要先压right因为我们想要先处理left。在栈结构里最后放进去的东西会最先被弹出来。所以先把右边的“存着”处理完左边那一条线后再回来处理右边。复杂度分析时间复杂度O ( n ) O(n)O(n)。每个节点都被访问且仅访问一次。空间复杂度O ( n ) O(n)O(n)。最坏情况下树呈链状递归栈或手动栈的深度会达到n nn。中序遍历In-order Traversal是二叉树最常用的遍历方式之一特别是在**二叉搜索树BST**中中序遍历的结果恰好是升序排列的。1. 记住口诀左 - 根 - 右中序遍历的逻辑顺序是首先递归地访问左子树 (Left)。然后访问根节点 (Root)。最后递归地访问右子树 (Right)。2. 解法一递归法极其简单你只需要在“前序遍历”的基础上把记录值的语句res.append挪到两次递归调用中间即可。classSolution:definorderTraversal(self,root:Optional[TreeNode])-List[int]:res[]defdfs(node):ifnotnode:return# 1. 左一直往左走dfs(node.left)# 2. 根走不动了再记录当前值res.append(node.val)# 3. 右最后看右边dfs(node.right)dfs(root)returnres3. 解法二迭代法面试重点迭代法实现中序遍历比前序遍历稍微复杂一点因为访问节点的顺序和处理节点的顺序是不一致的。我们需要先“潜入”到最左端的叶子节点。逻辑一路向左只要当前节点不为空就把它压入栈并继续往左走。弹出并记录左边走到底了从栈中弹出一个节点这就是当前的“根”记录它的值。转向右边处理完根节点后把指针指向它的右孩子重复上述过程。classSolution:definorderTraversal(self,root:Optional[TreeNode])-List[int]:res[]stack[]currroot# curr 不为空或者栈不为空就继续whilecurrorstack:# 步骤 1一路向左扎到底whilecurr:stack.append(curr)currcurr.left# 步骤 2弹出栈顶元素最左或最近的根currstack.pop()res.append(curr.val)# 步骤 3转向右子树currcurr.rightreturnres4. 为什么中序遍历很重要排序属性如果你对一棵“二叉搜索树”进行中序遍历得到的结果一定是从小到大排好序的数组。验证搜索树判断一棵树是否是二叉搜索树LeetCode 98最简单的方法就是看它的中序遍历是否是递增的。总结三种遍历的递归区别前序记录- 左 - 右先看到根再看子树中序左 -记录- 右先看完左边回头看根再看右边后序左 - 右 -记录最后才看根常用于计算树的高度或删除树后序遍历Post-order Traversal是三种遍历中最“内敛”的一种。它的特点是必须等左右子树全部处理完才处理根节点。1. 记住口诀左 - 右 - 根后序遍历的逻辑顺序是首先递归地访问左子树 (Left)。然后递归地访问右子树 (Right)。最后访问根节点 (Root)。2. 解法一递归法依然是那三行核心代码只是顺序变了。它是计算树的高度104题或删除整棵树时的标准做法。classSolution:defpostorderTraversal(self,root:Optional[TreeNode])-List[int]:res[]defdfs(node):ifnotnode:returndfs(node.left)# 1. 左dfs(node.right)# 2. 右res.append(node.val)# 3. 根dfs(root)returnres3. 解法二迭代法“偷懒”镜像反转法后序遍历的迭代法如果正着写非常复杂因为你需要判断右子树是否已经访问过。但有一个神级脑筋急转弯前序遍历是根 - 左 - 右如果我们稍微改下顺序写成根 - 右 - 左把这个结果整体反转 (Reverse)就会得到左 - 右 - 根——这正是后序遍历classSolution:defpostorderTraversal(self,root:Optional[TreeNode])-List[int]:ifnotroot:return[]stack[root]res[]# 按照 根 - 右 - 左 的顺序入栈whilestack:nodestack.pop()res.append(node.val)# 因为是栈先压左后压右弹出来的就是先右后左ifnode.left:stack.append(node.left)ifnode.right:stack.append(node.right)# 最后把 [根, 右, 左] 反转成 [左, 右, 根]returnres[::-1]4. 为什么后序遍历很有用后序遍历体现了**“自底向上”**的思想。计算树的高度你需要知道左子树多高右子树多高然后取最大值加 1根节点。计算子树节点和你必须先算出左右两边的和才能算出包含当前根的总和。最近公共祖先 (LCA)通过后序遍历向上回溯信息。三种遍历的直观总结想象一棵树你拿着一支笔沿着树的外围轮廓走一圈从根左侧出发绕一圈回到根右侧前序遍历在经过节点的左侧时记录它。中序遍历在经过节点的底部时记录它。后序遍历在经过节点的右侧时记录它。知识点大串联到目前为止我们已经横跨了三个大领域线性结构链表双指针、快慢指针、数组滑动窗口、原地翻转。数学模拟大数加法进位处理、补零逻辑。树形结构二叉树前中后序递归与迭代。发现**“栈 (Stack)”和“递归”**其实是双胞胎层序遍历Level-order Traversal与之前的前、中、后序遍历完全不同。前三种属于深度优先遍历DFS而层序遍历属于广度优先遍历BFS。它像剥洋葱一样从根节点开始一层一层地由上到下、由左到右访问所有节点。1. 核心工具队列Queue实现层序遍历的关键在于使用“队列”这种先进先出FIFO的数据结构入队把根节点放进队列。循环只要队列不为空记录当前层的节点个数确定这层有多少人。依次弹出这些节点。把它们的左、右孩子如果有依次加入队列末尾。2. 代码实现 (Python)fromcollectionsimportdequeclassSolution:deflevelOrder(self,root:Optional[TreeNode])-List[List[int]]:ifnotroot:return[]res[]# 使用 deque双端队列popleft() 的时间复杂度为 O(1)queuedeque([root])whilequeue:# 1. 确定当前层有多少个节点level_sizelen(queue)current_level[]# 2. 连续处理 level_size 个节点保证它们属于同一层for_inrange(level_size):nodequeue.popleft()current_level.append(node.val)# 3. 将下一层的孩子节点加入队列ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)# 4. 将这一层的结果加入大列表res.append(current_level)returnres3. 为什么需要level_size len(queue)这是层序遍历最关键的一步。因为队列在不断地添加新节点下一层的孩子如果不提前固定当前层的数量while循环就会一直跑下去你无法区分哪些节点属于第一层哪些属于第二层。通过len(queue)我们给当前层画了一个“圈”保证for循环只处理这一层的节点。4. 复杂度分析时间复杂度O ( N ) O(N)O(N)。每个节点入队和出队各一次。空间复杂度O ( N ) O(N)O(N)。在最坏情况下比如满二叉树最后一层的节点数大约是N / 2 N/2N/2队列需要存储这些节点。5. 常见变形题层序遍历的模版非常强大稍微改动就能解决很多问题二叉树的最大深度层序遍历跑了多少个while循环深度就是多少。二叉树的右视图每一层for循环结束时的最后一个节点就是从右边看到的节点。之字形遍历根据层数的奇偶性反转current_level列表。总结DFS vs BFS特性DFS (前中后序)BFS (层序)数据结构栈 (Stack) / 递归队列 (Queue)特点一条路走到黑再回溯稳扎稳打层层推进适用场景路径搜索、找祖先、树结构更改最短路径、层级统计