【代码随想录算法训练营第13天】二叉树part01 | 递归遍历 | 迭代遍历 | 层序遍历（注：统一迭代没看，以后看）-北京尧图网络

文章目录KEY1二叉树理论1 前中后遍历直接在每个节点的前中后地方画点遍历即可2 二叉树节点的定义2用TreeNode *存储节点T1 二叉树的递归遍历前中后序1 递归套路思路2 前中后的代码思路具体完整代码前序(中、后只是把那三行代码的顺序变一下)T2 二叉树的迭代遍历1 前序整个代码2 后序注意翻转reverse(res.begin(),res.end());3 中序T3 二叉树的层序遍历注意和我们平时理解的图的BFS有一点区别他这个题目要求输出每层的节点每次进入新的一层开始一个新的while循环时用 int size记录下当前这一层的节点数量注意每次入栈/入队都要判断一下节点是否为空root; left; right层序遍历的10题已完成部分题解如下总体不难107.二叉树的层次遍历 II199.二叉树的右视图429.N叉树的层序遍历515.在每个树行中找最大值注:统一迭代没看以后看KEY1二叉树理论1 前中后遍历直接在每个节点的前中后地方画点遍历即可2 二叉树节点的定义structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(NULL),right(NULL){}};2用TreeNode *存储节点eg.queueTreeNode*q;T1 二叉树的递归遍历前中后序1 递归套路思路确定递归函数的参数和返回值确定终止条件确定单层递归的逻辑2 前中后的代码思路注意递归遍历函数的输入输出是void preoder(TreeNode* cur, vectorint res)然后再用一个大函数vectorint preorderTraversal(TreeNode* root)包起来具体完整代码前序(中、后只是把那三行代码的顺序变一下)/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */classSolution{public:voidpreoder(TreeNode*cur,vectorintres){if(curnullptr){return;}res.push_back(cur-val);preoder(cur-left,res);preoder(cur-right,res);}vectorintpreorderTraversal(TreeNode*root){vectorintres;preoder(root,res);returnres;}};T2 二叉树的迭代遍历1 前序还好思路简单但是注意考虑树为空的情况和左右子树为空的情况整个代码class Solution{public:vectorintpreorderTraversal(TreeNode*root){stackTreeNode*st;vectorintres;//注意要考虑树为空的情况if(rootnullptr)returnres;st.push(root);TreeNode*curnullptr;while(!st.empty()){curst.top();res.push_back(cur-val);st.pop();if(cur-right)st.push(cur-right);if(cur-left)st.push(cur-left);}returnres;}};2 后序思路前序中左右后序左右中前序的左右两个push语句反过来中右左- 再翻转左右中注意翻转reverse(res.begin(),res.end());代码classSolution{public:vectorintpostorderTraversal(TreeNode*root){stackTreeNode*st;vectorintres;//注意要考虑树为空的情况if(rootnullptr)returnres;st.push(root);TreeNode*curnullptr;while(!st.empty()){curst.top();res.push_back(cur-val);st.pop();if(cur-left)st.push(cur-left);if(cur-right)st.push(cur-right);}reverse(res.begin(),res.end());returnres;}};3 中序思路迭代法的话不好和前后的代码统一有方法看代码随想录我没看问题遍历节点的时候你遍历到的节点和你要处理的节点不一样怎么办用一个栈记录遍历到的节点用一个指针指向当前遍历到的节点具体思路先一路向左遍历每个遍历到的点都入栈直到到了空节点处理中间节点即栈顶元素遍历它的右节点classSolution{public:vectorintinorderTraversal(TreeNode*root){TreeNode*curroot;vectorintresult;stackTreeNode*st;while(cur!nullptr||!st.empty()){// 一路向左遍历入栈while(cur!nullptr){st.push(cur);curcur-left;}// 已经到最左了处理中curst.top();st.pop();result.push_back(cur-val);// 处理右子树curcur-right;}returnresult;}};T3 二叉树的层序遍历注意和我们平时理解的图的BFS有一点区别他这个题目要求输出每层的节点每次进入新的一层开始一个新的while循环时用int size记录下当前这一层的节点数量注意每次入栈/入队都要判断一下节点是否为空root; left; rightclassSolution{public:vectorvectorintlevelOrder(TreeNode*root){queueTreeNode*que;vectorvectorintresult;TreeNode*cur;intsize;// 记录当前这一层的元素个数if(root)que.push(root);//每次入栈/入队都要判断一下节点是否为空while(!que.empty()){sizeque.size();vectorintvec;while(size--){curque.front();que.pop();vec.push_back(cur-val);if(cur-left)que.push(cur-left);if(cur-right)que.push(cur-right);}result.push_back(vec);}returnresult;}};层序遍历的10题已完成部分题解如下总体不难107.二叉树的层次遍历 II不用看。相对于102.二叉树的层序遍历就是最后把result数组反转一下就可以了注意翻转是这个语法reverse(result.begin(),result.end());199.二叉树的右视图不用看。相对于102.二叉树的层序遍历就是每次把每层的最后一个元素收集起来即可429.N叉树的层序遍历不用看知道就好。改一小段处理字节点的代码即可for(inti0;icur-children.size();i){Node*childcur-children[i];if(child)que.push(child);}515.在每个树行中找最大值注意这个赋值int max INT_MIN;另如何表示 -2^32int val pow(-2, 31);注:统一迭代没看以后看

【代码随想录算法训练营第13天】二叉树part01 | 递归遍历 | 迭代遍历 | 层序遍历（注：统一迭代没看，以后看）

相关推荐

如何从零开始构建3D实时战略游戏：OpenRTS完整入门指南

密码遗忘困扰你？3步掌握LaZagne找回丢失的凭据

意念控制机器人：从脑机接口到远程意念指令的无限可能

更多资讯

完整剖析 better-douyin Open Shell：Mock Bridge 与 Mock Backend 是如何设计的

四类垃圾3000张标注数据集实战：从数据清洗到模型训练全流程

AI赋能集成电路教育：从知识切片到数字化平台建设路径

还在对着静态桌面发呆？DyberPet 5 分钟装好，让屏幕右下角替你盯梢

【基于Qt5仿音乐播放器（五）】——数据持久化

从野蛮生长到合规深耕：储能行业新标闭环，重塑全产业链安全逻辑，捷思特解决方案赋能产业升级！

今日更新

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？