企业官网建设流程全解析

站长网seo综合查询工具,学生个人网页,海西州电子商务网站建设,广州官网优化用一个栈搞定二叉树前/中/后序遍历#xff08;非递归版#xff09;#xff1a;把递归“翻译”成 while 循环 很多人写递归遍历很顺手#xff0c;但一到非递归就开始迷糊#xff1a;栈怎么压#xff1f;什么时候弹#xff1f;为什么后序还要 prev#xff1f; 其实核心只…用一个栈搞定二叉树前/中/后序遍历非递归版把递归“翻译”成 while 循环很多人写递归遍历很顺手但一到非递归就开始迷糊栈怎么压什么时候弹为什么后序还要prev其实核心只有一句话非递归遍历 用显式栈模拟递归调用栈再用“访问时机”决定前/中/后序。三种遍历的区别不在“走法”而在“什么时候把节点加入结果”。前序第一次见到节点就访问根最早中序左边走到底后弹栈时访问根居中后序左右都处理完最后才访问根最晚所以需要额外信息判断“右子树是否已经处理过”下面按你给的三段代码逐段讲。0. 先统一一个“心智模型”栈里装的是什么递归遍历时每次函数调用会把“当前节点”和“接下来要做的事”压到调用栈里。非递归就是把“当前节点”手动压到stack并用cur指针控制下一步去哪。常见骨架长这样while(cur!null||!stack.isEmpty()){while(cur!null){stack.push(cur);curcur.left;}// 到这里说明左链走到底了TreeNodetopstack.pop()or stack.peek();// ...访问 or 转向右子树...}差别在前序压栈时就访问中序弹栈时访问后序满足“左右都完成”才弹栈并访问1) 中序遍历左-根-右非递归最经典模板中序代码classSolution{publicListIntegerinorderTraversal(TreeNoderoot){//左根右StackTreeNodestacknewStack();ListIntegerlistnewArrayList();TreeNodecurroot;while(cur!null||!stack.isEmpty()){while(cur!null){stack.push(cur);curcur.left;}TreeNodetopstack.pop();list.add(top.val);curtop.right;}returnlist;}}过程讲解像在走图Step A一路向左“钻到底”沿途压栈while(cur!null){stack.push(cur);curcur.left;}这一步把从当前节点出发的“左链”全部压栈。压栈顺序大概就是根、根的左、左的左……Step B左边到头了开始“回溯”TreeNodetopstack.pop();list.add(top.val);curtop.right;pop()代表递归里“左子树做完了回到当前节点”此时访问top就实现了“左-根”然后cur top.right转向右子树继续同样流程为什么是中序因为访问发生在左子树处理完之后、右子树开始之前刚好是“左根右”的根位置。✅ 这份代码可以当作中序非递归的“标准答案模板”。2) 后序遍历左-右-根非递归关键在prev后序代码classSolution{publicListIntegerpostorderTraversal(TreeNoderoot){ListIntegerlistnewArrayList();if(rootnull)returnlist;StackTreeNodestacknewStack();TreeNodecurroot;TreeNodeprevnull;while(cur!null||!stack.isEmpty()){while(cur!null){stack.push(cur);curcur.left;}TreeNodetopstack.peek();if(top.rightnull||top.rightprev){list.add(top.val);stack.pop();prevtop;}else{curtop.right;}}returnlist;}}为什么后序比中序难后序要“根最后访问”。但当左链走到底时栈顶节点的左子树确实做完了——可右子树可能还没做。所以不能像中序那样直接pop()访问。这就是prev的意义prev记录“刚刚完成访问出栈的节点”用它判断右子树是不是已经处理过。过程拆解核心分支只看这一段TreeNodetopstack.peek();if(top.rightnull||top.rightprev){// 右子树为空 或 右子树刚处理完visit(top);pop(top);prevtop;}else{// 右子树存在且没处理curtop.right;}情况 1top.right null右子树为空那就说明左子树已经完成因为能来到 peek右子树不存在所以当前节点可以访问根最后情况 2top.right prev这句是精髓“栈顶节点的右孩子刚刚被访问完”说明右子树已经处理完毕。于是当前节点也满足“左右都完成”可以访问并出栈。情况 3右子树存在且未处理这时候不能访问根必须先去右子树curtop.right;然后循环会再次走 “一路向左压栈”把右子树的左链压进去。为什么这一定是后序因为每个节点只有在左子树完成且右子树完成之后才会被访问根必然最后。⭐ 易错点重点标识如果没有prev很容易在“从右子树回来”时无法判断是否该访问根导致反复进入右子树或死循环。peek()必须配合条件判断这里不能直接pop()否则会提前访问根顺序变坏。3) 前序遍历根-左-右非递归访问时机前移前序代码classSolution{publicListIntegerpreorderTraversal(TreeNoderoot){ListIntegerlistnewArrayList();if(rootnull)returnlist;StackTreeNodestacknewStack();TreeNodecurroot;stack.push(cur);while(!stack.isEmpty()){while(cur!null){stack.push(cur);list.add(cur.val);curcur.left;}TreeNodetopstack.pop();curtop.right;}returnlist;}}先讲它的核心思想前序要求“根最先访问”。所以访问时机要比中序更早第一次遇到节点就访问。你这份代码确实做到了在压栈时就list.add(cur.val)。while(cur!null){stack.push(cur);list.add(cur.val);curcur.left;}然后左链走完弹一个节点出来转向它的右子树TreeNodetopstack.pop();curtop.right;但这里有个小提醒实现细节这段代码里有一行stack.push(cur);// 进入 while 前又 push 了一次 root而在循环里又stack.push(cur)因此根节点会被压栈两次不过访问只发生一次所以结果通常不受影响但栈操作会冗余逻辑也不够干净。更常见、更“干净”的前序非递归写法通常是下面两种之一写法 A一路向左访问并压栈不需要额外先 pushpublicListIntegerpreorderTraversal(TreeNoderoot){ListIntegerresnewArrayList();DequeTreeNodestacknewArrayDeque();TreeNodecurroot;while(cur!null||!stack.isEmpty()){while(cur!null){res.add(cur.val);// 前序先访问stack.push(cur);curcur.left;}TreeNodetopstack.pop();curtop.right;}returnres;}写法 B标准“栈模拟”模板弹出就访问先压右再压左publicListIntegerpreorderTraversal(TreeNoderoot){ListIntegerresnewArrayList();if(rootnull)returnres;DequeTreeNodestacknewArrayDeque();stack.push(root);while(!stack.isEmpty()){TreeNodenodestack.pop();res.add(node.val);if(node.right!null)stack.push(node.right);if(node.left!null)stack.push(node.left);}returnres;}两种都对。写法 A 和你中序的骨架更一致适合“统一模板记忆”写法 B 很直观适合初学者。4) 三种遍历的对照总结差别只在“访问时机”把三段代码放在一起看其实只改了一个点什么时候把top.val加进结果。遍历顺序非递归共同骨架访问时机前序根-左-右左链压栈 转右压栈/第一次遇到节点时访问中序左-根-右左链压栈 转右弹栈时访问左完成后后序左-右-根左链压栈 条件转右左右都完成时访问靠prev判断5) 最容易踩的坑建议贴在笔记顶部后序一定要有“右子树是否处理完”的判断没有prev或等价机制极容易死循环或顺序错。中序的关键动作是pop 后访问再转 right少一步都会乱序。前序的关键是访问要发生在走左之前把add放到 pop 后就变成中序/后序味道了。尽量用ArrayDeque代替Stack工程上更推荐Stack是老类继承自 Vector同步开销大Deque更现代更快。算法逻辑不变。结尾把递归“翻译”成迭代的诀窍真正的诀窍不是背代码而是把递归的三件事想明白递归“往下走” → 用cur和while(cur ! null)模拟递归“回到父节点” → 用stack保存路径前/中/后序的区别 →访问发生在下潜前 / 回溯时 / 左右都完成后理解到这层换题、换写法都不会慌。