数组、链表、栈、队列这些线性结构我相信很多人学完以后觉得自己数据结构入门了。可真到了面试或者实际项目里遇到树形结构相关的题目大部分人立马就露馅了。树是第一种真正意义上非线性的数据结构也是从会用工具到理解结构之间的一道分水岭。这篇内容是我整理《恋上数据结构第1季》二叉树部分的学习笔记结合了刷题和实际写代码的经验重点把二叉树基础、真二叉树、满二叉树、完全二叉树的判定逻辑以及二叉树的遍历这个重难点掰开揉碎讲清楚。无论你是刚开始学数据结构的在校生还是准备跳槽想补基础的后端开发者这份笔记都值得你花二十分钟慢慢读。市面上讲二叉树的资料非常多但普遍存在两个问题一是概念讲得太散真二叉树、满二叉树、完全二叉树之间的区别说了半天还是晕二是遍历只讲递归写法一问到迭代怎么写就卡壳。所以这篇文章我会把概念对比和遍历实现放在同等重要的位置每个结论都附带可以直接上手的判断方法和代码套路不是在背概念而是真正让你看完能写、写完能跑、跑完能讲明白。1. 为什么二叉树是数据结构的分水岭以及最容易被忽略的基础术语很多初学者对树的第一个困惑是我数组、链表已经能存数据了为什么要搞出树这种东西答案其实很简单——线性结构解决的是一对一的关系而现实世界里大量数据是一对多的比如文件系统的目录结构、公司组织架构、网页里的DOM节点。二叉树作为最基础的树形结构它把一对多的问题简化成最多两个孩子既保留了树的表达能力又让计算变得可行。这也是为什么几乎所有教材都把二叉树作为树的入门形态而不是直接讲多叉树。1.1 节点关系的精确表述父子、兄弟、祖先、后代在动手写代码之前有几个术语必须先钉死不然后面讲遍历的时候你会听懵。根节点整棵树最顶层的那个节点一棵树只有一个根。父节点与子节点边连接的两个节点靠近根的叫父远离根的叫子。兄弟节点同一个父节点下的多个子节点互为兄弟。叶子节点度为0的节点也就是没有孩子的节点。子树任何一个节点连同它的所有后代构成一棵子树。这个理解非常关键——遍历的操作对象本质上是子树。还有一个容易混淆的概念节点的度。节点的度指的是它拥有的子节点数量。二叉树的约束就是每个节点的度最大为2即最多两个子节点并且分左右不能颠倒。1.2 高度、深度和层数的计算误区层数、深度、高度这三个概念几乎是初学阶段混乱的重灾区。我直接给你一个不会被搞晕的口径层数Level根节点在第1层往下递增。深度Depth从根节点到当前节点所经过的边数。有的教材定义根节点深度为0有的定义为1不同语境下会有区别。但如果你用经过的边数来定义根节点深度就是0它的子节点深度就是1这样在任何场合都不会出错。高度Height从当前节点到最远叶子节点经过的边数。叶子节点高度为0。以一棵只有根节点的树为例层数为1深度为0高度为0。以一棵三层满二叉树为例第三层叶子节点的深度是2高度为0根节点的深度是0高度为2。整棵树的高度等于根节点的高度。这里我建议你养成一个习惯写到代码注释里时统一标注深度边数这样即使换教材也不会对不上号。面试时如果面试官问深度从0还是1开始直接回答我习惯用边数定义根节点深度为0一个清晰的回答比模棱两可好得多。2. 真二叉树、满二叉树、完全二叉树三种特殊形态的终极分辨指南标题里的三个概念——真二叉树、满二叉树、完全二叉树——很多人看完定义就忘原因在于教科书把三个概念分开讲没有放一起对比。实际上它们之间是有严格的包含关系的理解了这层关系你只需要记一条主线。2.1 真二叉树只关心有没有单分支的特殊形态真二叉树的定义是所有节点的度要么是0要么是2绝对不允许出现度为1的节点。换句话说每一个非叶子节点都必须同时拥有左孩子和右孩子。为什么要把这种形态单独拎出来定义因为很多算法和数据结构性质在没有单分支节点的前提下会变得非常漂亮。比如后面你学哈夫曼树Huffman Tree的时候哈夫曼树就是一棵真二叉树再比如表达式的二叉树表示每个内部节点都代表一个运算符运算符必须要有两个操作数所以它天然就是真二叉树。判断真二叉树的代码逻辑很简单遍历每一个节点如果某个节点度为1直接判定不是真二叉树。时间复杂度O(n)没有捷径。2.2 满二叉树每一层都塞满的完美身材满二叉树的定义更严格每一层的节点数都达到最大值也就是说最后一层也是满的。这棵树从画面上看就是一个完整的等腰三角形没有任何缺角。满二叉树有一个极强的数学性质如果高度为h边数那么整棵树的节点总数 n 2^(h1) - 1。比如高度为0的满二叉树就是单个根节点节点数1公式算出来是2^1 - 1 1没问题。高度为2的满二叉树节点数应该是2^3 - 1 7。这里必须提一个名词差异的坑国内很多教材把满二叉树定义为每一层都满但部分翻译教材会把每个节点度为0或2的树也叫做满二叉树Full Binary Tree。我在实际学习中发现《恋上数据结构》这门课为了绕开这个歧义引入了真二叉树这个词来特指度为0或2的情况把每一层都满的树称为满二叉树。这个分化很好大家在读其他资料时留个心眼看到英文Full Binary Tree时先确认上下文到底在说哪种。2.3 完全二叉树只有最后一层能缺而且缺的只能是右边完全二叉树的定义比满二叉树宽松一些但比真二叉树严格从上到下、从左到右编号所有节点必须和同高度的满二叉树编号一一对应。用人话说就是节点按层从左往右排列中间不能有空档最后一层可以不满但缺失的节点只能出现在最后一层的靠右位置。完全二叉树有两个判断要点是面试中特别容易踩坑的地方第一如果某个节点只有左孩子没有右孩子那么它必须位于最后一层。如果它不在最后一层这棵树就不是完全二叉树。第二一旦层序遍历过程中遇到了一个空位那么此后再也不允许出现非空节点。这一点是编写算法判断完全二叉树的核心思路。完全二叉树在实际工程里非常重要因为它是可以用数组存储的树。堆Heap就是一棵完全二叉树用数组下标2i1和2i2就能表示左右孩子的位置关系完全不需要指针极大地节省了内存和访问开销。2.4 三者的包含关系与快速判断表类型度为1的节点最后一层状态每层是否必须满典型应用真二叉树不允许任意否哈夫曼树、表达式树满二叉树不允许必须满是完美形态、数学推导完全二叉树至多一个可以不满但必须靠左连续除最后一层外必须满堆、优先队列三者关系满二叉树一定是真二叉树也一定是完全二叉树完全二叉树不一定是真二叉树也不一定是满二叉树真二叉树不一定完全也不一定满。2.5 完全二叉树节点数的性质推导完全二叉树还有一个高频考察点给定n个节点如何快速计算叶子节点数结论是叶子节点数等于 n/2 向上取整即ceil(n/2)。这个结论看起来像魔术其实推起来就一步。完全二叉树中度为1的节点至多只有1个。设度为0、1、2的节点数分别为n0、n1、n2则 n n0 n1 n2。又因为边数等于节点数减1即 n - 1 n1 2*n2。两式相减可以得到 n0 n2 1。当n为偶数时n11n0 n/2当n为奇数时n10n0 (n1)/2。合并起来就是ceil(n/2)。这个推导过程其实不需要背现场推一遍也就半分钟但考试时直接套结论能省很多时间。3. 四种遍历方式的核心原理与手写套路重点标题里括号标注了重点这正是二叉树部分真正的硬核内容。遍历听起来简单——把每个节点访问一遍——但真正的难点在于三种深度优先遍历前序、中序、后序之间的顺序关系以及如何把递归写法改写成迭代写法。我见过太多人递归背得滚瓜烂熟一写迭代就大脑空白。3.1 前序遍历根节点最先被访问前序遍历的顺序是根-左-右。也就是说对任意一棵子树先访问子树的根节点再递归遍历左子树最后递归遍历右子树。前序遍历的一个直观记忆法你从根节点出发沿着树的左边一路向下走每经过一个节点就访问它到了左边尽头再回头处理右边的分支。所以前序序列的第一个元素必定是整棵树的根节点。递归写法没什么好说的三行代码void preorder(TreeNode* node) { if (node nullptr) return; visit(node-val); // 访问根 preorder(node-left); // 遍历左子树 preorder(node-right); // 遍历右子树 }迭代写法就值得好好说了。核心思路是用显式栈模拟系统调用栈。注意一个细节因为栈是后进先出为了保证先左后右的处理顺序我们压栈时就要先压右子树再压左子树这样弹出的时候左子树会先被处理。void preorderIterative(TreeNode* root) { if (root nullptr) return; stackTreeNode* stk; stk.push(root); while (!stk.empty()) { TreeNode* node stk.top(); stk.pop(); visit(node-val); if (node-right) stk.push(node-right); // 先压右 if (node-left) stk.push(node-left); // 再压左 } }这里我特别提醒一句很多人会把压栈顺序记反导致输出结果变成了根-右-左。如果你也容易混那就想一个画面——右孩子是后进的它在栈的更上面但它本来就应该更晚访问顺序正好反着来所以必须先压它。3.2 中序遍历中序序列与二叉搜索树的奇妙的关联中序遍历的顺序是左-根-右。它有一个极其重要的性质对一棵二叉搜索树BST做中序遍历得到的序列一定是递增有序的。这也是为什么中序遍历被单独列出来反复考察。递归写法依然很直接void inorder(TreeNode* node) { if (node nullptr) return; inorder(node-left); visit(node-val); inorder(node-right); }迭代写法比前序要稍微绕一点核心思想是一路向左从根节点出发不断把左孩子压栈直到左孩子为空然后弹出栈顶节点访问再转向它的右子树重复这个过程。void inorderIterative(TreeNode* root) { stackTreeNode* stk; TreeNode* cur root; while (cur ! nullptr || !stk.empty()) { while (cur ! nullptr) { // 一路向左压栈 stk.push(cur); cur cur-left; } cur stk.top(); stk.pop(); visit(cur-val); // 访问栈顶 cur cur-right; // 转向右子树 } }这个当前指针cur的写法是很多经典教材的标准实现。和递归版本对比着看你会发现一个有趣的对应关系递归版本中的inorder(node-left)对应迭代版本里的while (cur ! nullptr)向左压栈递归调用返回的场景就是栈弹出访问完根之后调用inorder(node-right)就对应cur cur-right。把这两组对应关系想透迭代写法就不再是背代码而是真正理解了。3.3 后序遍历三个版本里最需要技巧的迭代实现后序遍历左-右-根递归不难但迭代写起来最麻烦因为根节点是最后才访问的意味着你无法像前序那样在第一次碰到节点时就访问也无法像中序那样在弹栈时马上访问——你得确认右子树处理完了才能访问根。一种比较直观的实现方式是使用两个栈或者用一个栈加一个上一次访问的节点指针。我个人推荐用记录上一次访问节点的方法理解起来更顺面试时也不容易写错。void postorderIterative(TreeNode* root) { stackTreeNode* stk; TreeNode* cur root; TreeNode* lastVisited nullptr; while (cur ! nullptr || !stk.empty()) { while (cur ! nullptr) { // 一路向左压栈 stk.push(cur); cur cur-left; } TreeNode* top stk.top(); // 如果右子树为空或者右子树刚刚访问完就可以访问当前节点 if (top-right nullptr || top-right lastVisited) { visit(top-val); stk.pop(); lastVisited top; } else { cur top-right; // 否则先处理右子树 } } }这个方法的巧妙之处在于lastVisited这个指针。当top-right lastVisited时说明右子树已经被完整遍历过了继续访问当前节点不会破坏后序顺序。如果你觉得这个版本还是复杂可以退一步用前序逆序的取巧法前序顺序是根-左-右把前序改成根-右-左再整体逆序就得到左-右-根也就是后序。这种办法只需要改前序迭代里压栈的顺序然后结果收集到数组里最后反转是一种能应急的备选方案。3.4 层序遍历队列的应用题同时也是完全二叉树判定的帮手层序遍历宽度优先搜索要求从上到下、从左到右一层一层访问。它的迭代实现是所有遍历里最好写的因为完全贴合队列的先进先出特性每访问一个节点就把它的左右孩子依次入队。void levelOrder(TreeNode* root) { if (root nullptr) return; queueTreeNode* q; q.push(root); while (!q.empty()) { TreeNode* node q.front(); q.pop(); visit(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } }层序遍历最常见的升级问题是按层输出要求把每一层的节点分别放到一个小数组里。这时需要在每一层开始时先记录q.size()因为这一层的节点数就是当前队列的长度。循环处理完这批节点队列里剩下的正好是下一层的全部节点。这个技巧在处理二叉树相关题目时使用非常普遍值得熟练掌握。层序遍历还可以用来解决一个更基础的问题计算树的高度。因为每遍历一层高度就加1所以只需要在按层输出的基础上加一个计数器即可。4. 用前序/后序 中序还原二叉树遍历序列的真正考场遍历不只是用来输出的面试里更常见的考察方式是反过来给你两种遍历序列让你还原出这棵二叉树。这个题目几乎逢面必考值得单独拿出来说。4.1 为什么中序序列是还原的关键先记住一个原则还原二叉树必须要有中序序列。为什么因为前序序列的第一个元素是根节点但它没法告诉你哪些节点属于左子树、哪些属于右子树。而中序序列的特点是根节点把序列一分为二左边全是左子树节点右边全是右子树节点。举一个具体例子。假设前序序列是 A B D E C F中序序列是 D B E A F C。前序的第一个元素是A所以A是根。在中序序列中找到A它的左边是 D B E右边是 F C。因此左子树包含 D、B、E右子树包含 F、C。接下来递归处理左子树前序序列在A之后紧跟着 B D E第一个元素是B所以B是左子树的根。在中序 D B E 中找到B左侧D是B的左孩子右侧E是B的右孩子。右子树同理前序里 C 是右子树根中序 F C 中F在C左侧所以F是C的左孩子。这种做法的核心就是不断重复用前序找根再用中序分割左右递归处理每个子树。后序 中序的原理完全一样区别只在于后序序列的最后一个元素才是根。4.2 边界条件与前序后序不能还原的原因如果你见过前序后序的还原题可能会疑惑给这两个序列不也能确定一些信息吗答案是不一定能唯一确定一棵二叉树。原因在于前序和后序都只提供根的位置信息但无法区分某个节点是左孩子还是右孩子。考虑一棵只有两个节点的二叉树前序是 A B后序是 B A。这棵树可能是A的左孩子为B也可能是A的右孩子为B。前序后序的信息完全不足以区分这两种情况。只有在真二叉树所有内部节点都有两个孩子的前提下前序后序才能唯一还原。4.3 手写还原过程的代码框架递归还原的代码框架其实很短以前序中序为例TreeNode* buildTree(vectorint preorder, vectorint inorder) { int preIndex 0; unordered_mapint, int inorderIndex; for (int i 0; i inorder.size(); i) { inorderIndex[inorder[i]] i; } return build(preorder, inorder, inorderIndex, 0, inorder.size() - 1, preIndex); } TreeNode* build(vectorint preorder, vectorint inorder, unordered_mapint, int map, int inLeft, int inRight, int preIndex) { if (inLeft inRight) return nullptr; int rootVal preorder[preIndex]; TreeNode* root new TreeNode(rootVal); int inMid map[rootVal]; root-left build(preorder, inorder, map, inLeft, inMid - 1, preIndex); root-right build(preorder, inorder, map, inMid 1, inRight, preIndex); return root; }用一个哈希表提前存储中序序列每个值的位置可以把查找根节点位置的耗时从O(n)降为O(1)。整体时间复杂度是O(n)空间复杂度主要消耗在哈希表和递归栈上。5. 工程实战二叉树遍历真实应用场景与选型建议讨论完概念和代码再花点篇幅讲讲这些知识在实际项目中到底怎么用。很多人学完数据结构之后觉得做题有用工作没用其实只是因为没找到对应场景。5.1 表达式求值与解析树后序遍历的真实案例编译器在处理算术表达式时会把表达式解析成一棵二叉树内部节点是运算符叶子节点是数字。比如表达式(1 2) * (3 - 4)根节点是*左子树是(1 2)右子树是(3 - 4)。要计算这棵表达式的值只需要做一次后序遍历先算左子树的值再算右子树的值最后用根节点的运算符做计算。后序先孩子后父母的顺序恰好对应了运算优先级——你不可能在不知道两个操作数的情况下先做加法。理解了这一点再看后序遍历就会觉得这个别扭的顺序其实非常自然。5.2 文件目录结构序列化前序遍历帮你拍平一棵树当你要把一棵树存到数据库或者传输给另一个服务时通常需要把它序列化成字符串。二叉树序列化最常用的方式就是前序遍历每个节点存值空节点用特殊标记比如#占位。前序序列化后空节点的位置信息也保留在字符串里因此反序列化时只要照着前序的顺序重建即可不需要额外的分隔信息。如果你用中序序列化就会出问题空节点的左右位置无法区分反序列化会出现歧义。这也是为什么工程里做二叉树序列化基本都选前序或层序中序只适合人类阅读排序结果。5.3 二叉堆与优先队列完全二叉树的工程地位前面提到过堆必须建立在完全二叉树之上因为它用数组存储下标布局紧凑没有空洞。优先队列就是堆的典型实现。当你用priority_queue往里面推入元素时底层就在不断调整完全二叉树的结构维护堆序性质。这时候完全二叉树的概念不是停留在纸面上的定义而是实实在在影响着数组扩容策略、下滤操作的路径长度等实现细节。5.4 递归转迭代的性能考量心得我自己的经验是在工程代码里项目里递归写起来最爽但如果树的深度可能超过几千层递归方案就容易触发栈溢出这时候必须转迭代。比如遍历一个深度为十万的树递归版本的调用栈压力不是开玩笑的。再比如某些嵌入式环境或者协程环境里系统栈很小迭代写法几乎是唯一可行方案。不过迭代写的代码可读性确实不如递归所以我一般建议在代码里保留递归版本并加注释性能敏感路径再单独写迭代版本。不要一上来就追求全部迭代那样反而容易引入不易察觉的边界bug。6. 学习路径与记忆锚点如何把二叉树知识变成条件反射最后这部分写给正在跟着课程学习的读者。二叉树的内容不难但知识点多、细、相互关联强没有好的记忆锚点很容易学了就忘。我分享几个自己验证过有效的办法。6.1 用遍历出口判断三种深度优先顺序每次默写三种深度优先遍历时不要死记根左右、左根右、左右根而是只看一个位置根节点出现在三个位置里的哪一个。根在前就是前序根在中就是中序根在后就是后序。这个记忆锚点最简洁面对子树嵌套时也不会搞混。6.2 用一个固定demo树反复手写四种遍历找一棵固定的树比如1 / \ 2 3 / \ \ 4 5 6反复手写它的四种遍历结果直到形成肌肉记忆。前序1 2 4 5 3 6中序4 2 5 1 3 6后序4 5 2 6 3 1层序1 2 3 4 5 6。这棵树在刷题时非常常用因为它的结构非对称——有的节点有左没右有的有右没左有的左右都有覆盖的情况足够全面。拿它验证你写的任何遍历代码都不会漏边界。6.3 把完全二叉树的判断条件与层序遍历绑定记忆完全二叉树的判断代码有很多版本我最推荐的是层序遍历遇到第一个空节点后队列中剩余的所有节点必须全部为null否则就不是完全二叉树。把这个条件和层序遍历绑在一起记忆一举两得既复习了层序又掌握了完全二叉树的判定算法。bool isComplete(TreeNode* root) { if (root nullptr) return true; queueTreeNode* q; q.push(root); bool seenEmpty false; while (!q.empty()) { TreeNode* node q.front(); q.pop(); if (node nullptr) { seenEmpty true; } else { if (seenEmpty) return false; q.push(node-left); q.push(node-right); } } return true; }这段代码的巧妙之处在于它把空节点也入队了。一旦遇到过null之后只要再出现非null节点说明树的节点排列不满足从上到下、从左到右连续的要求直接返回false。边界情况叶子节点的左右孩子都是null入队后会在后面被依次消费不影响判断。6.4 建议的学习顺序如果让我给初学者排一个二叉树学习路线我会这样建议先掌握节点定义和基础术语再画图理解三种特殊形态然后死磕递归遍历能默写之后立刻挑战迭代写法最后做遍历序列还原二叉树的题目。每一步都以前一步为基础不要跳。我在带新人的时候发现凡是跳过递归直接背迭代的后面遇到复杂树题目基本都会翻车凡是觉得概念太简单不想看的写判断完全二叉树的时候总会漏掉度为1节点的边界。写到这里我自己也把二叉树这部分的知识点重新梳理了一遍。回头看《恋上数据结构第1季》这门课里二叉树章节之所以花大量篇幅讲真、满、完全三种形态确实是因为这些概念是后续堆、二叉搜索树、AVL树、红黑树的前提。把这篇笔记里的代码都自己敲过一遍之后再往后学的时候会明显觉得阻力小很多。我这里给出的判断方法和遍历写法都是经过我反复验证的通用套路不需要引入额外框架或依赖复制到本地跑一跑就能见效。
数组、链表、栈、队列这些线性结构我相信很多人学完以后觉得自己数据结构入门了。可真到了面试或者实际项目里遇到树形结构相关的题目大部分人立马就露馅了。树是第一种真正意义上非线性的数据结构也是从会用工具到理解结构之间的一道分水岭。这篇内容是我整理《恋上数据结构第1季》二叉树部分的学习笔记结合了刷题和实际写代码的经验重点把二叉树基础、真二叉树、满二叉树、完全二叉树的判定逻辑以及二叉树的遍历这个重难点掰开揉碎讲清楚。无论你是刚开始学数据结构的在校生还是准备跳槽想补基础的后端开发者这份笔记都值得你花二十分钟慢慢读。市面上讲二叉树的资料非常多但普遍存在两个问题一是概念讲得太散真二叉树、满二叉树、完全二叉树之间的区别说了半天还是晕二是遍历只讲递归写法一问到迭代怎么写就卡壳。所以这篇文章我会把概念对比和遍历实现放在同等重要的位置每个结论都附带可以直接上手的判断方法和代码套路不是在背概念而是真正让你看完能写、写完能跑、跑完能讲明白。1. 为什么二叉树是数据结构的分水岭以及最容易被忽略的基础术语很多初学者对树的第一个困惑是我数组、链表已经能存数据了为什么要搞出树这种东西答案其实很简单——线性结构解决的是一对一的关系而现实世界里大量数据是一对多的比如文件系统的目录结构、公司组织架构、网页里的DOM节点。二叉树作为最基础的树形结构它把一对多的问题简化成最多两个孩子既保留了树的表达能力又让计算变得可行。这也是为什么几乎所有教材都把二叉树作为树的入门形态而不是直接讲多叉树。1.1 节点关系的精确表述父子、兄弟、祖先、后代在动手写代码之前有几个术语必须先钉死不然后面讲遍历的时候你会听懵。根节点整棵树最顶层的那个节点一棵树只有一个根。父节点与子节点边连接的两个节点靠近根的叫父远离根的叫子。兄弟节点同一个父节点下的多个子节点互为兄弟。叶子节点度为0的节点也就是没有孩子的节点。子树任何一个节点连同它的所有后代构成一棵子树。这个理解非常关键——遍历的操作对象本质上是子树。还有一个容易混淆的概念节点的度。节点的度指的是它拥有的子节点数量。二叉树的约束就是每个节点的度最大为2即最多两个子节点并且分左右不能颠倒。1.2 高度、深度和层数的计算误区层数、深度、高度这三个概念几乎是初学阶段混乱的重灾区。我直接给你一个不会被搞晕的口径层数Level根节点在第1层往下递增。深度Depth从根节点到当前节点所经过的边数。有的教材定义根节点深度为0有的定义为1不同语境下会有区别。但如果你用经过的边数来定义根节点深度就是0它的子节点深度就是1这样在任何场合都不会出错。高度Height从当前节点到最远叶子节点经过的边数。叶子节点高度为0。以一棵只有根节点的树为例层数为1深度为0高度为0。以一棵三层满二叉树为例第三层叶子节点的深度是2高度为0根节点的深度是0高度为2。整棵树的高度等于根节点的高度。这里我建议你养成一个习惯写到代码注释里时统一标注深度边数这样即使换教材也不会对不上号。面试时如果面试官问深度从0还是1开始直接回答我习惯用边数定义根节点深度为0一个清晰的回答比模棱两可好得多。2. 真二叉树、满二叉树、完全二叉树三种特殊形态的终极分辨指南标题里的三个概念——真二叉树、满二叉树、完全二叉树——很多人看完定义就忘原因在于教科书把三个概念分开讲没有放一起对比。实际上它们之间是有严格的包含关系的理解了这层关系你只需要记一条主线。2.1 真二叉树只关心有没有单分支的特殊形态真二叉树的定义是所有节点的度要么是0要么是2绝对不允许出现度为1的节点。换句话说每一个非叶子节点都必须同时拥有左孩子和右孩子。为什么要把这种形态单独拎出来定义因为很多算法和数据结构性质在没有单分支节点的前提下会变得非常漂亮。比如后面你学哈夫曼树Huffman Tree的时候哈夫曼树就是一棵真二叉树再比如表达式的二叉树表示每个内部节点都代表一个运算符运算符必须要有两个操作数所以它天然就是真二叉树。判断真二叉树的代码逻辑很简单遍历每一个节点如果某个节点度为1直接判定不是真二叉树。时间复杂度O(n)没有捷径。2.2 满二叉树每一层都塞满的完美身材满二叉树的定义更严格每一层的节点数都达到最大值也就是说最后一层也是满的。这棵树从画面上看就是一个完整的等腰三角形没有任何缺角。满二叉树有一个极强的数学性质如果高度为h边数那么整棵树的节点总数 n 2^(h1) - 1。比如高度为0的满二叉树就是单个根节点节点数1公式算出来是2^1 - 1 1没问题。高度为2的满二叉树节点数应该是2^3 - 1 7。这里必须提一个名词差异的坑国内很多教材把满二叉树定义为每一层都满但部分翻译教材会把每个节点度为0或2的树也叫做满二叉树Full Binary Tree。我在实际学习中发现《恋上数据结构》这门课为了绕开这个歧义引入了真二叉树这个词来特指度为0或2的情况把每一层都满的树称为满二叉树。这个分化很好大家在读其他资料时留个心眼看到英文Full Binary Tree时先确认上下文到底在说哪种。2.3 完全二叉树只有最后一层能缺而且缺的只能是右边完全二叉树的定义比满二叉树宽松一些但比真二叉树严格从上到下、从左到右编号所有节点必须和同高度的满二叉树编号一一对应。用人话说就是节点按层从左往右排列中间不能有空档最后一层可以不满但缺失的节点只能出现在最后一层的靠右位置。完全二叉树有两个判断要点是面试中特别容易踩坑的地方第一如果某个节点只有左孩子没有右孩子那么它必须位于最后一层。如果它不在最后一层这棵树就不是完全二叉树。第二一旦层序遍历过程中遇到了一个空位那么此后再也不允许出现非空节点。这一点是编写算法判断完全二叉树的核心思路。完全二叉树在实际工程里非常重要因为它是可以用数组存储的树。堆Heap就是一棵完全二叉树用数组下标2i1和2i2就能表示左右孩子的位置关系完全不需要指针极大地节省了内存和访问开销。2.4 三者的包含关系与快速判断表类型度为1的节点最后一层状态每层是否必须满典型应用真二叉树不允许任意否哈夫曼树、表达式树满二叉树不允许必须满是完美形态、数学推导完全二叉树至多一个可以不满但必须靠左连续除最后一层外必须满堆、优先队列三者关系满二叉树一定是真二叉树也一定是完全二叉树完全二叉树不一定是真二叉树也不一定是满二叉树真二叉树不一定完全也不一定满。2.5 完全二叉树节点数的性质推导完全二叉树还有一个高频考察点给定n个节点如何快速计算叶子节点数结论是叶子节点数等于 n/2 向上取整即ceil(n/2)。这个结论看起来像魔术其实推起来就一步。完全二叉树中度为1的节点至多只有1个。设度为0、1、2的节点数分别为n0、n1、n2则 n n0 n1 n2。又因为边数等于节点数减1即 n - 1 n1 2*n2。两式相减可以得到 n0 n2 1。当n为偶数时n11n0 n/2当n为奇数时n10n0 (n1)/2。合并起来就是ceil(n/2)。这个推导过程其实不需要背现场推一遍也就半分钟但考试时直接套结论能省很多时间。3. 四种遍历方式的核心原理与手写套路重点标题里括号标注了重点这正是二叉树部分真正的硬核内容。遍历听起来简单——把每个节点访问一遍——但真正的难点在于三种深度优先遍历前序、中序、后序之间的顺序关系以及如何把递归写法改写成迭代写法。我见过太多人递归背得滚瓜烂熟一写迭代就大脑空白。3.1 前序遍历根节点最先被访问前序遍历的顺序是根-左-右。也就是说对任意一棵子树先访问子树的根节点再递归遍历左子树最后递归遍历右子树。前序遍历的一个直观记忆法你从根节点出发沿着树的左边一路向下走每经过一个节点就访问它到了左边尽头再回头处理右边的分支。所以前序序列的第一个元素必定是整棵树的根节点。递归写法没什么好说的三行代码void preorder(TreeNode* node) { if (node nullptr) return; visit(node-val); // 访问根 preorder(node-left); // 遍历左子树 preorder(node-right); // 遍历右子树 }迭代写法就值得好好说了。核心思路是用显式栈模拟系统调用栈。注意一个细节因为栈是后进先出为了保证先左后右的处理顺序我们压栈时就要先压右子树再压左子树这样弹出的时候左子树会先被处理。void preorderIterative(TreeNode* root) { if (root nullptr) return; stackTreeNode* stk; stk.push(root); while (!stk.empty()) { TreeNode* node stk.top(); stk.pop(); visit(node-val); if (node-right) stk.push(node-right); // 先压右 if (node-left) stk.push(node-left); // 再压左 } }这里我特别提醒一句很多人会把压栈顺序记反导致输出结果变成了根-右-左。如果你也容易混那就想一个画面——右孩子是后进的它在栈的更上面但它本来就应该更晚访问顺序正好反着来所以必须先压它。3.2 中序遍历中序序列与二叉搜索树的奇妙的关联中序遍历的顺序是左-根-右。它有一个极其重要的性质对一棵二叉搜索树BST做中序遍历得到的序列一定是递增有序的。这也是为什么中序遍历被单独列出来反复考察。递归写法依然很直接void inorder(TreeNode* node) { if (node nullptr) return; inorder(node-left); visit(node-val); inorder(node-right); }迭代写法比前序要稍微绕一点核心思想是一路向左从根节点出发不断把左孩子压栈直到左孩子为空然后弹出栈顶节点访问再转向它的右子树重复这个过程。void inorderIterative(TreeNode* root) { stackTreeNode* stk; TreeNode* cur root; while (cur ! nullptr || !stk.empty()) { while (cur ! nullptr) { // 一路向左压栈 stk.push(cur); cur cur-left; } cur stk.top(); stk.pop(); visit(cur-val); // 访问栈顶 cur cur-right; // 转向右子树 } }这个当前指针cur的写法是很多经典教材的标准实现。和递归版本对比着看你会发现一个有趣的对应关系递归版本中的inorder(node-left)对应迭代版本里的while (cur ! nullptr)向左压栈递归调用返回的场景就是栈弹出访问完根之后调用inorder(node-right)就对应cur cur-right。把这两组对应关系想透迭代写法就不再是背代码而是真正理解了。3.3 后序遍历三个版本里最需要技巧的迭代实现后序遍历左-右-根递归不难但迭代写起来最麻烦因为根节点是最后才访问的意味着你无法像前序那样在第一次碰到节点时就访问也无法像中序那样在弹栈时马上访问——你得确认右子树处理完了才能访问根。一种比较直观的实现方式是使用两个栈或者用一个栈加一个上一次访问的节点指针。我个人推荐用记录上一次访问节点的方法理解起来更顺面试时也不容易写错。void postorderIterative(TreeNode* root) { stackTreeNode* stk; TreeNode* cur root; TreeNode* lastVisited nullptr; while (cur ! nullptr || !stk.empty()) { while (cur ! nullptr) { // 一路向左压栈 stk.push(cur); cur cur-left; } TreeNode* top stk.top(); // 如果右子树为空或者右子树刚刚访问完就可以访问当前节点 if (top-right nullptr || top-right lastVisited) { visit(top-val); stk.pop(); lastVisited top; } else { cur top-right; // 否则先处理右子树 } } }这个方法的巧妙之处在于lastVisited这个指针。当top-right lastVisited时说明右子树已经被完整遍历过了继续访问当前节点不会破坏后序顺序。如果你觉得这个版本还是复杂可以退一步用前序逆序的取巧法前序顺序是根-左-右把前序改成根-右-左再整体逆序就得到左-右-根也就是后序。这种办法只需要改前序迭代里压栈的顺序然后结果收集到数组里最后反转是一种能应急的备选方案。3.4 层序遍历队列的应用题同时也是完全二叉树判定的帮手层序遍历宽度优先搜索要求从上到下、从左到右一层一层访问。它的迭代实现是所有遍历里最好写的因为完全贴合队列的先进先出特性每访问一个节点就把它的左右孩子依次入队。void levelOrder(TreeNode* root) { if (root nullptr) return; queueTreeNode* q; q.push(root); while (!q.empty()) { TreeNode* node q.front(); q.pop(); visit(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } }层序遍历最常见的升级问题是按层输出要求把每一层的节点分别放到一个小数组里。这时需要在每一层开始时先记录q.size()因为这一层的节点数就是当前队列的长度。循环处理完这批节点队列里剩下的正好是下一层的全部节点。这个技巧在处理二叉树相关题目时使用非常普遍值得熟练掌握。层序遍历还可以用来解决一个更基础的问题计算树的高度。因为每遍历一层高度就加1所以只需要在按层输出的基础上加一个计数器即可。4. 用前序/后序 中序还原二叉树遍历序列的真正考场遍历不只是用来输出的面试里更常见的考察方式是反过来给你两种遍历序列让你还原出这棵二叉树。这个题目几乎逢面必考值得单独拿出来说。4.1 为什么中序序列是还原的关键先记住一个原则还原二叉树必须要有中序序列。为什么因为前序序列的第一个元素是根节点但它没法告诉你哪些节点属于左子树、哪些属于右子树。而中序序列的特点是根节点把序列一分为二左边全是左子树节点右边全是右子树节点。举一个具体例子。假设前序序列是 A B D E C F中序序列是 D B E A F C。前序的第一个元素是A所以A是根。在中序序列中找到A它的左边是 D B E右边是 F C。因此左子树包含 D、B、E右子树包含 F、C。接下来递归处理左子树前序序列在A之后紧跟着 B D E第一个元素是B所以B是左子树的根。在中序 D B E 中找到B左侧D是B的左孩子右侧E是B的右孩子。右子树同理前序里 C 是右子树根中序 F C 中F在C左侧所以F是C的左孩子。这种做法的核心就是不断重复用前序找根再用中序分割左右递归处理每个子树。后序 中序的原理完全一样区别只在于后序序列的最后一个元素才是根。4.2 边界条件与前序后序不能还原的原因如果你见过前序后序的还原题可能会疑惑给这两个序列不也能确定一些信息吗答案是不一定能唯一确定一棵二叉树。原因在于前序和后序都只提供根的位置信息但无法区分某个节点是左孩子还是右孩子。考虑一棵只有两个节点的二叉树前序是 A B后序是 B A。这棵树可能是A的左孩子为B也可能是A的右孩子为B。前序后序的信息完全不足以区分这两种情况。只有在真二叉树所有内部节点都有两个孩子的前提下前序后序才能唯一还原。4.3 手写还原过程的代码框架递归还原的代码框架其实很短以前序中序为例TreeNode* buildTree(vectorint preorder, vectorint inorder) { int preIndex 0; unordered_mapint, int inorderIndex; for (int i 0; i inorder.size(); i) { inorderIndex[inorder[i]] i; } return build(preorder, inorder, inorderIndex, 0, inorder.size() - 1, preIndex); } TreeNode* build(vectorint preorder, vectorint inorder, unordered_mapint, int map, int inLeft, int inRight, int preIndex) { if (inLeft inRight) return nullptr; int rootVal preorder[preIndex]; TreeNode* root new TreeNode(rootVal); int inMid map[rootVal]; root-left build(preorder, inorder, map, inLeft, inMid - 1, preIndex); root-right build(preorder, inorder, map, inMid 1, inRight, preIndex); return root; }用一个哈希表提前存储中序序列每个值的位置可以把查找根节点位置的耗时从O(n)降为O(1)。整体时间复杂度是O(n)空间复杂度主要消耗在哈希表和递归栈上。5. 工程实战二叉树遍历真实应用场景与选型建议讨论完概念和代码再花点篇幅讲讲这些知识在实际项目中到底怎么用。很多人学完数据结构之后觉得做题有用工作没用其实只是因为没找到对应场景。5.1 表达式求值与解析树后序遍历的真实案例编译器在处理算术表达式时会把表达式解析成一棵二叉树内部节点是运算符叶子节点是数字。比如表达式(1 2) * (3 - 4)根节点是*左子树是(1 2)右子树是(3 - 4)。要计算这棵表达式的值只需要做一次后序遍历先算左子树的值再算右子树的值最后用根节点的运算符做计算。后序先孩子后父母的顺序恰好对应了运算优先级——你不可能在不知道两个操作数的情况下先做加法。理解了这一点再看后序遍历就会觉得这个别扭的顺序其实非常自然。5.2 文件目录结构序列化前序遍历帮你拍平一棵树当你要把一棵树存到数据库或者传输给另一个服务时通常需要把它序列化成字符串。二叉树序列化最常用的方式就是前序遍历每个节点存值空节点用特殊标记比如#占位。前序序列化后空节点的位置信息也保留在字符串里因此反序列化时只要照着前序的顺序重建即可不需要额外的分隔信息。如果你用中序序列化就会出问题空节点的左右位置无法区分反序列化会出现歧义。这也是为什么工程里做二叉树序列化基本都选前序或层序中序只适合人类阅读排序结果。5.3 二叉堆与优先队列完全二叉树的工程地位前面提到过堆必须建立在完全二叉树之上因为它用数组存储下标布局紧凑没有空洞。优先队列就是堆的典型实现。当你用priority_queue往里面推入元素时底层就在不断调整完全二叉树的结构维护堆序性质。这时候完全二叉树的概念不是停留在纸面上的定义而是实实在在影响着数组扩容策略、下滤操作的路径长度等实现细节。5.4 递归转迭代的性能考量心得我自己的经验是在工程代码里项目里递归写起来最爽但如果树的深度可能超过几千层递归方案就容易触发栈溢出这时候必须转迭代。比如遍历一个深度为十万的树递归版本的调用栈压力不是开玩笑的。再比如某些嵌入式环境或者协程环境里系统栈很小迭代写法几乎是唯一可行方案。不过迭代写的代码可读性确实不如递归所以我一般建议在代码里保留递归版本并加注释性能敏感路径再单独写迭代版本。不要一上来就追求全部迭代那样反而容易引入不易察觉的边界bug。6. 学习路径与记忆锚点如何把二叉树知识变成条件反射最后这部分写给正在跟着课程学习的读者。二叉树的内容不难但知识点多、细、相互关联强没有好的记忆锚点很容易学了就忘。我分享几个自己验证过有效的办法。6.1 用遍历出口判断三种深度优先顺序每次默写三种深度优先遍历时不要死记根左右、左根右、左右根而是只看一个位置根节点出现在三个位置里的哪一个。根在前就是前序根在中就是中序根在后就是后序。这个记忆锚点最简洁面对子树嵌套时也不会搞混。6.2 用一个固定demo树反复手写四种遍历找一棵固定的树比如1 / \ 2 3 / \ \ 4 5 6反复手写它的四种遍历结果直到形成肌肉记忆。前序1 2 4 5 3 6中序4 2 5 1 3 6后序4 5 2 6 3 1层序1 2 3 4 5 6。这棵树在刷题时非常常用因为它的结构非对称——有的节点有左没右有的有右没左有的左右都有覆盖的情况足够全面。拿它验证你写的任何遍历代码都不会漏边界。6.3 把完全二叉树的判断条件与层序遍历绑定记忆完全二叉树的判断代码有很多版本我最推荐的是层序遍历遇到第一个空节点后队列中剩余的所有节点必须全部为null否则就不是完全二叉树。把这个条件和层序遍历绑在一起记忆一举两得既复习了层序又掌握了完全二叉树的判定算法。bool isComplete(TreeNode* root) { if (root nullptr) return true; queueTreeNode* q; q.push(root); bool seenEmpty false; while (!q.empty()) { TreeNode* node q.front(); q.pop(); if (node nullptr) { seenEmpty true; } else { if (seenEmpty) return false; q.push(node-left); q.push(node-right); } } return true; }这段代码的巧妙之处在于它把空节点也入队了。一旦遇到过null之后只要再出现非null节点说明树的节点排列不满足从上到下、从左到右连续的要求直接返回false。边界情况叶子节点的左右孩子都是null入队后会在后面被依次消费不影响判断。6.4 建议的学习顺序如果让我给初学者排一个二叉树学习路线我会这样建议先掌握节点定义和基础术语再画图理解三种特殊形态然后死磕递归遍历能默写之后立刻挑战迭代写法最后做遍历序列还原二叉树的题目。每一步都以前一步为基础不要跳。我在带新人的时候发现凡是跳过递归直接背迭代的后面遇到复杂树题目基本都会翻车凡是觉得概念太简单不想看的写判断完全二叉树的时候总会漏掉度为1节点的边界。写到这里我自己也把二叉树这部分的知识点重新梳理了一遍。回头看《恋上数据结构第1季》这门课里二叉树章节之所以花大量篇幅讲真、满、完全三种形态确实是因为这些概念是后续堆、二叉搜索树、AVL树、红黑树的前提。把这篇笔记里的代码都自己敲过一遍之后再往后学的时候会明显觉得阻力小很多。我这里给出的判断方法和遍历写法都是经过我反复验证的通用套路不需要引入额外框架或依赖复制到本地跑一跑就能见效。
