1. 二叉树的概念与核心性质刷题前先把底子打牢很多朋友拿到二叉树题目就一头扎进去写代码结果写到一半发现连节点数、叶子数的公式都推导不明白选择题更是全靠蒙。我见过太多人卡在“二叉树的遍历”和“求深度”这类基础题上不是代码不会写而是对二叉树的基本性质没有真正吃透。这里先把最核心的几个性质梳理一遍因为后面所有算法题和选择题本质都在围着它们打转。1.1 从结构定义到关键公式二叉树就是每个节点最多有两个子树的树结构分别叫左子树和右子树左、右的顺序不能颠倒。在C语言里一个最普通的二叉树节点长这样typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;这个结构体就是几乎所有二叉树题目的“地基”data存值lchild和rchild分别指向左右孩子。没有子树的位置就用NULL也就是空指针。很多同学的代码跑着跑着就段错误十有八九是访问了 NULL 的子树这点先记下来。接着是三个绕不开的公式选择题特别喜欢考性质1非空二叉树的第 i 层上最多有 2^(i-1) 个节点。这个可以从根节点往下推每一层最多是上一层的两倍。性质2深度为 k 的二叉树节点总数最多为 2^k - 1。性质3叶子节点数 n0 等于度为2的节点数 n2 加 1也就是 n0 n2 1。性质3特别重要它其实是考试和面试的高频点。它的推导思路并不复杂一棵二叉树的总节点数 n n0 n1 n2其中 n1 是度为1的节点数。而总分支数边数一定等于 n - 1同时分支数也等于 n1 2*n2。两边一联立n - 1 n1 2*n2把 n n0 n1 n2 代进去化简就得到 n0 n2 1。1.2 满二叉树与完全二叉树别把概念混在一起选择题里出现频率极高的另一组概念是“满二叉树”和“完全二叉树”。满二叉树是指每一层的节点数都达到最大值也就是深度为 k 的满二叉树正好有 2^k - 1 个节点每一层都是满的。完全二叉树则是指除最后一层外每一层都是满的且最后一层的节点都集中在左边连续的位置。可以这样理解完全二叉树就是一棵拿满二叉树从最底层最右边开始“删节点”得到的树删掉之后依然保持从上到下、从左到右连续。这两者的关系是满二叉树一定是完全二叉树但完全二叉树不一定是满二叉树。选择题经常给一棵树让你判断这里有个简单办法——把节点按满二叉树的方式编号如果所有节点都连续排在最左侧就是完全二叉树。编号规律也很实用假设节点的编号为 i如果 2i 存在则左孩子编号为 2i如果 2i1 存在则右孩子编号为 2i1。反过来父亲节点的编号是 i/2 向下取整。这个规律在后面的数组存储和选择题里会反复用到。2. 二叉树的遍历前序、中序、后序、层序必须门儿清遍历是二叉树算法题里最基础的“基本功”。前序、中序、后序这三种深度优先遍历加上层序这种广度优先遍历几乎是一切二叉树题目的载体。你后续做的求深度、构造二叉树、求公共祖先底层都依赖遍历框架。2.1 递归遍历三行代码里的访问时机递归遍历的代码本身极短难点在于你什么时候“访问”节点。先看三个经典版本// 前序遍历根左右 void PreOrder(BiTree T) { if (T NULL) return; visit(T); // 访问根节点 PreOrder(T-lchild); PreOrder(T-rchild); } // 中序遍历左根右 void InOrder(BiTree T) { if (T NULL) return; InOrder(T-lchild); visit(T); InOrder(T-rchild); } // 后序遍历左右根 void PostOrder(BiTree T) { if (T NULL) return; PostOrder(T-lchild); PostOrder(T-rchild); visit(T); }三个版本的结构几乎一样只是 visit 的位置不同。前序是在递归左子树之前访问所以根最先被处理中序是先递归左子树再访问于是左子树全部输出后才轮到根后序则是左右子树都递归完了再访问根。我经常和学生说递归遍历的代码不要求死背理解“访问时机”更重要。最简单的记忆方法看名字。前序就是根在最前面中序是根在中间后序是根在最后面。左子树的访问永远在右子树之前这跟二叉树左子树优先的结构定义有关。2.2 非递归遍历用栈模拟系统调用递归遍历本质上依赖函数调用栈但有些场景比如树特别深不允许递归或者面试官就要求手写非递归版本这时候你得会用栈模拟递归过程。这里最容易写错的是中序和后序我一个个说。先看前序非递归。它的逻辑很直观根节点入栈弹出栈顶元素并访问然后先把右子树压栈再压左子树这样出栈时左子树会先被访问void PreOrderIter(BiTree T) { if (T NULL) return; Stack S; initStack(S); push(S, T); while (!isEmpty(S)) { BiTNode *p pop(S); visit(p); if (p-rchild) push(S, p-rchild); if (p-lchild) push(S, p-lchild); } }中序非递归则是尽量往左走走到最左端后弹出节点访问再转向右子树void InOrderIter(BiTree T) { Stack S; initStack(S); BiTNode *p T; while (p || !isEmpty(S)) { if (p) { push(S, p); p p-lchild; } else { p pop(S); visit(p); p p-rchild; } } }很多人初次接触这段代码时会卡住为什么 p 是空的时候才 pop因为中序要先处理左子树所以一路向左压栈直到没有左孩子为止这时候才轮到栈顶节点。后序非递归最麻烦因为根节点必须在左右子树都访问完之后才输出你无法确定从栈里弹出节点时它的右子树是否已经访问过了。常用的办法是加一个标记位或者用两个栈void PostOrderIter(BiTree T) { if (T NULL) return; Stack S1, S2; initStack(S1); initStack(S2); push(S1, T); while (!isEmpty(S1)) { BiTNode *p pop(S1); push(S2, p); if (p-lchild) push(S1, p-lchild); if (p-rchild) push(S1, p-rchild); } while (!isEmpty(S2)) { visit(pop(S2)); } }双栈法的原理是S1 的出栈顺序是“根右左”因为先压左后压右而 S1 弹出的每个节点都压进 S2最后 S2 出栈顺序恰好是“左右根”也就是后序。层序遍历则是完全不同的思路用队列从上到下、从左到右逐层处理void LevelOrder(BiTree T) { if (T NULL) return; Queue Q; initQueue(Q); enQueue(Q, T); while (!isEmpty(Q)) { BiTNode *p deQueue(Q); visit(p); if (p-lchild) enQueue(Q, p-lchild); if (p-rchild) enQueue(Q, p-rchild); } }层序的框架在后面求二叉树宽度、输出每层节点时会反复用到建议直接背下来当模板。2.3 从遍历序列恢复二叉树选择题和算法题的热点给定前序中序、或者后序中序可以唯一确定一棵二叉树。这是选择题的必考点也是算法题常客。原理很简单前序或后序遍历第一个或最后一个节点是根节点而中序遍历中根的左边就是左子树的中序序列右边是右子树的中序序列再结合前序或后序序列中左右子树的长度就能递推还原整棵树。举个例子前序遍历序列是 ABDGCEF中序遍历序列是 DGBAECF。前序的第一个节点是 A所以根是 A。在中序里找到 A左边是 DGB右边是 ECF。这意味着左子树的中序是 DGB右子树的中序是 ECF。再看前序除开 A 后是 BDGCEF由于左子树有 3 个节点所以前序里 B 是左子树的根DG 是 B 的左子树前序中序里 B 左边是 DG所以 B 是根DG 是 B 的左孩子……依此类推可以完整恢复出树的形状。这里有个容易踩的坑前序后序一般不能唯一确定二叉树。原因在于当前序和后序都只能知道根的位置但如果某个节点只有左子树或只有右子树两种序列无法区分到底是左还是右。只有在满二叉树这种特殊情况下前序后序才能唯一确定。选择题经常会出这个判断题答案永远是有中序才唯一。3. 必刷经典算法题从深度到公共祖先的完整解法遍历框架掌握以后很多算法题就是“换一层皮”。下面这几个题我按由易到难排列都是二叉树学习中最常被点名考察的代码我给了 C 或 Python 版本方便你对照理解。3.1 求二叉树的深度最大深度深度就是从根节点到最远叶子节点的节点数。递归解法非常简洁def maxDepth(root): if not root: return 0 return max(maxDepth(root.left), maxDepth(root.right)) 1这段代码我建议倒背如流递归出口是空节点返回0非空节点的高度等于左右子树高度的较大值再加1。它的本质是后序遍历因为你得先把左右子树的高度算出来才能知道当前节点的高度。如果面试官不给递归也可以用层序遍历来数层数每处理完一层计数器加1队列里存的恰好是当前层的所有节点。3.2 求叶子节点数、节点总数这两种题就是遍历加统计的问题。叶子节点是指没有左孩子也没有右孩子的节点。可以用任意遍历方式在访问节点时判断int countLeaf(BiTree T) { if (T NULL) return 0; if (T-lchild NULL T-rchild NULL) return 1; return countLeaf(T-lchild) countLeaf(T-rchild); }节点总数更简单就是左子树节点数加右子树节点数再加1int countNode(BiTree T) { if (T NULL) return 0; return countNode(T-lchild) countNode(T-rchild) 1; }这两个题看起来基础但可以秒杀一批选择题。比如完全二叉树有 700 个节点问叶子节点有多少个。你要注意到完全二叉树的节点个数可以推出层数和最后一层的情况然后结合 n0 n2 1 和总节点公式来算。3.3 翻转二叉树翻转二叉树就是求它的镜像把每个节点的左右子树都交换。递归写法极其简洁def invertTree(root): if not root: return None root.left, root.right invertTree(root.right), invertTree(root.left) return root关键点在于你必须先递归处理子树再交换指针。如果先交换再递归也可以但要注意递归的对象是交换后的子树不要传错。这个题曾经是某大厂面试的“送分题”结果挂了不少人——原因不是不会代码而是有人觉得题目里没让讲思路就直接写忽略了“交换指针”这个关键步骤要解释清楚。3.4 判断一棵二叉树是否平衡平衡二叉树的定义是任意节点的左右子树高度差不超过1。常规解法是自顶向下每个节点都算一次左右子树高度再递归判断下去。但这样每个节点会被重复计算高度时间复杂度 O(n^2)。更优的解法是自底向上在求高度的过程中同时判断是否平衡def isBalanced(root): def height(node): if not node: return 0 left_h height(node.left) if left_h -1: return -1 right_h height(node.right) if right_h -1: return -1 if abs(left_h - right_h) 1: return -1 return max(left_h, right_h) 1 return height(root) ! -1这里把“不平衡”用 -1 来表示好处是省去了单独写 isBalanced 递归的麻烦一次遍历就能得出结果。这种“在递归返回值里附加状态信息”的思路在二叉树算法里特别常见比如后面的公共祖先问题也会用到类似的带状态递归思路。3.5 判断二叉树是否对称判断一棵二叉树是否关于根节点对称不能只看左右孩子相等而是要递归比较 left.left 和 right.right、left.right 和 right.left。原因是镜像对称时左子树的外侧要和右子树的外侧对应左子树的内侧要和右子树的内侧对应。def isSymmetric(root): def check(p, q): if not p and not q: return True if not p or not q: return False return p.val q.val and check(p.left, q.right) and check(p.right, q.left) return check(root.left, root.right) if root else True很多人第一次写会写成 check(left.left, right.left)结果当然不对。理解“外侧对外侧、内侧对内侧”是关键。3.6 最近公共祖先 LCA给定两个节点 p 和 q找它们在一棵普通二叉树里的最近公共祖先。递归解法是经典中的经典def lowestCommonAncestor(root, p, q): if not root or root p or root q: return root left lowestCommonAncestor(root.left, p, q) right lowestCommonAncestor(root.right, p, q) if left and right: return root return left if left else right这个递归的核心逻辑可以这样记如果当前节点是 p 或 q 之一直接返回当前节点如果左右递归都非空说明 p 和 q 分别位于当前节点的左右两侧那当前节点就是公共祖先如果只有一侧非空说明两个节点都在同一侧返回非空的那侧结果。实际面试时这道题经常变体如果是二叉搜索树BST可以利用节点值大小来剪枝左子树的祖先值小于根右子树的值大于根直接判断 p 和 q 与当前节点的相对大小就能决定往哪边走复杂度可以降到树高。3.7 路径和系列根到叶子路径“是否存在一条从根到叶子的路径使得路径上所有节点值之和等于 targetSum”这是个高频题递归写起来很流畅def hasPathSum(root, targetSum): if not root: return False if not root.left and not root.right and root.val targetSum: return True return hasPathSum(root.left, targetSum - root.val) or hasPathSum(root.right, targetSum - root.val)这里要注意的是递归函数传入的 targetSum 要减去当前节点的值表示“还差多少”。很多新手写成把 sum 累加传下去然后在叶子判断是否等于 targetSum也不是不行但容易在传参时搞混建议统一用“剩余需要量”的口径。如果题目进一步要求“找出所有满足条件的路径”那就要把当前路径记录下来并把符合条件的路径加入结果列表这就是经典的回溯模板。再延伸一下题目若改为“从一个节点出发路径不一定经过根或叶子但路径方向必须向下”难度就上来了。通常用前缀和 哈希表来优化遍历时记录从根到当前节点的累计和查哈希表里有多少个前缀和等于当前累计和减去 targetSum。这就是把二叉树和哈希表结合的典型考法最近几年面试热度很高。4. 高频选择题考点与易错题剖析选择题在数据结构考试里占了很大一块二叉树又是出题密集区。很多同学算法题能写出来但选择题居然会错原因往往是概念模糊、性质记混。下面我把最高频的几类选择题考点整理一下并给出快速解题的思路。4.1 节点数与叶子数的计算题这类题的突破口就两个公式n0 n2 1 和 总节点数 n n0 n1 n2。比如一棵二叉树有 10 个度为 2 的节点5 个度为 1 的节点问度为 0 的节点有多少个套公式叶子数 度为2节点数 1 11所以总节点数是 11 5 10 26。这个题能错的人基本都是把 n0 n2 1 和 n n0 n1 n2 给记岔了。还有一种变形完全二叉树有 500 个节点问叶子节点有多少。解这类题有个技巧完全二叉树的度为1节点数 n1 只能是 0 或 1。总节点 500 是偶数而 n0 n1 n2 500又因为 n0 n2 1所以 n1 2n2 1 500即 n1 2n2 499。499 是奇数说明 n1 必须是奇数所以 n1 1于是 n2 249n0 250。你看只需要三步就出答案。4.2 遍历序列推导题给出一棵二叉树的前序和中序让你选正确的后续或者给中序和后序选前序。这类题最稳妥的解法是先在草稿纸上把二叉树的结构恢复出来再按要求的顺序输出。如果你对恢复比较熟也可以直接根据序列特征判断。举一个小例子某二叉树的前序遍历为 ABC中序遍历为 BCA。前序第一个是 A说明 A 是根。在中序里 A 在最后说明 A 没有右子树整棵树都在 A 的左边。再看前序 B 在 A 后面所以 B 是 A 的左孩子。中序 B 后面是 C说明 C 是 B 的右孩子如果 C 是 B 的左孩子中序里 C 应该在 B 前面。所以后序是 CBA。这类题很容易在“B 的左孩子还是右孩子”上出错画图最稳妥。我建议考试时不要只靠脑内模拟动笔画出树正确率会高非常多。4.3 特殊二叉树的概念辨析二叉排序树BST、平衡二叉树AVL、哈夫曼树Huffman Tree、线索二叉树这四种特殊二叉树也是选择题重灾区。BST左子树所有节点值小于根右子树所有节点值大于根。中序遍历 BST 得到的是递增序列这个性质是选择题最常考的。在选择题里给你一棵树的插入序列让你判断形状或者给一棵树让你判断是不是 BST核心就是看“中序遍历是否有序”和“是否满足左小右大的递归定义”。AVL任何节点的左右子树高度差绝对值不超过1而且左右子树也都必须是 AVL。选择题里常给一组插入序列让你判断最终是否是平衡二叉树或者问插入后需要几次旋转。旋转分 LL、RR、LR、RL 四种这个可以单独写一篇这里先提醒一句LR 和 RL 要先旋转成 LL/RR 再整体旋转很多人在这里丢分。哈夫曼树带权路径长度WPL最小的二叉树只有度为0和2的节点没有度为1的节点。n 个叶子节点的哈夫曼树总节点数为 2n - 1。选择题常考 WPL 的计算构造步骤是每次取权值最小的两个节点合并。线索二叉树利用空指针域存放前驱和后继信息。中序线索二叉树里最左下角节点的前驱为空最右下角节点的后继为空。这个知识点出题频率不低主要是概念判断比如“中序线索二叉树中某节点的后继如何找”。4.4 选择题快解技巧很多同学在复习阶段花大量时间刷算法题但到了期末或者考研发现选择题才是拉开分数的关键。几个实用技巧特殊值代入法把树设成最简单的情形比如只有根节点、只有左子树、只有右子树用极端情况验证公式或概念。画图法凡是涉及遍历序列、节点数、深度的题直接用一棵小规模树画出来推快且准确。排除法配合性质比如判断完全二叉树可以先看节点编号是否连续或者直接用 2i 和 2i1 的编号规则去套。5. 刷题过程中的避坑经验与模板总结我把这些年刷二叉树题目遇到的高频问题整理成了几类这些坑我几乎每届学生都会踩一遍提前说清楚能帮你少走很多弯路。5.1 递归边界条件空节点永远是第一优先写递归二叉树题第一件事永远是判断当前节点是否为空。有个口诀我常挂在嘴边一切递归先判空。哪怕你已经知道“这里一定有孩子”也要写 if not root: return ...因为变量的名字和实际情况之间隔着很长的调用链一旦有空指针传入整个代码直接崩掉。有些同学担心多写判空影响性能其实影响微乎其微但安全性提升是巨大的。所有递归算法题空节点判断是安全和正确性的底座没有它后面的逻辑全是空中楼阁。5.2 非递归遍历时栈和队列的类型问题在用 C 语言手写非递归遍历时栈里存的是指针而不是值。有些同学把栈声明成了 int 类型硬把节点地址塞进去最后访问 p-data 的时候编译倒是能过运行直接段错误。写作时建议栈的元素类型写完整BiTNode*不要用void*再强转虽然技术上可行但容易滋生类型错误。层序遍历里的队列也是同样的问题。有人图省事用数组模拟队列结果数组开小了树层数稍多就溢出。不要省这点内存动态扩容的队列或者直接用 C 的 queue / Python 的 deque 更稳妥。5.3 递归和迭代的选择理论上所有递归都能改成迭代但有些题比如判断对称、求解公共祖先迭代版本写起来非常啰嗦实话说并没有太大必要。我的建议是面试或考试时优先写你最有把握、最不容易出错的写法。如果时间允许再提一版迭代写法作为加分项。很多人平时练了一堆“优雅写法”考场上却因为紧张把递归出口写错了这就很亏。反过来如果题目明确要求“不能用递归”你就要立刻切换思路用栈或队列模拟。这也说明平时非递归遍历不能完全丢至少前序和中序的非递归要能背下来。5.4 注意树是否为空、只有一个节点的边界有相当一部分选择题和面试题喜欢在这里做文章。比如“求二叉树的最大深度”根节点为空时答案是 0只有一个根节点时答案是 1。“判断是否是对称二叉树”空树被认为是 true根节点左右都是空也是 true。边界条件弄错一对答案就知道错得有多冤。我给学生的建议是所有二叉树递归题写完以后先在心里过三个用例——空树、单节点树、两层的满二叉树。这三个用例如果能通过绝大多数边界问题都能被覆盖到。5.5 刷题顺序与复习节奏二叉树的学习路径我建议这样走先彻底掌握二叉树的定义和性质再背熟四种遍历的代码然后刷深度、节点数、叶子数这些基础题再刷翻转、平衡、对称这些“形状判断”题最后挑战路径和、公共祖先、构造二叉树这些综合题。每做完一道题可以停下来想想这道题如果改成二叉搜索树解法会怎么变如果改成求所有路径而不是存在性回溯怎么写这样一道题能顶三道题。我在实际复习阶段还有一个习惯把所有遇到的二叉树性质公式n0 n2 1、完全二叉树高度公式、哈夫曼总节点公式等抄在一张纸上考前只看这张纸。不夸张地说选择题的一半分数就是靠这张纸拿下的。二叉树的题目说多不多说少也不少但本质上都是遍历框架加状态的组合。你把遍历理解透了边界条件写全了公式记熟了分数自然就上去了。很多人觉得二叉树难是因为把它当成了背题其实数据结构这块恰恰是理解越多、死记越少的科目。最后再分享一个小技巧做选择题的时候养成分步推演的习惯不在脑海里跳步特别是节点数和遍历序列的推导过程写下来永远比乱猜稳。刷算法题的时候坚持“每个递归先判空”和“边界三用例测试”这两条习惯养成了你会在后续碰到所有树相关题目时受益。