二叉树这块儿我跟着“代码随想录”的专题啃过一整轮前后加起来刷了六十多道题。说实话二叉树是所有数据结构里最容易让人产生“我好像会了一写就废”感觉的题型递归一看就懂自己动手就栈溢出遍历顺序背得滚瓜烂熟一到层序就不知道队列该干嘛更别提面试里动不动就让你手写一个判断平衡二叉树写完还有一堆边界 Case 等着你。这篇文章不是把题库再复述一遍而是把我实际刷题、写程序、调试报错中沉淀下来的东西梳理出来。适合正在刷二叉树专题、准备算法面试、或者被树的递归搞到头大的读者。1. 二叉树学习的整体思路与核心框架1.1 先从“怎么表示一棵树”说起写二叉树程序的人多半都经历过这样的开场定义结构体、写递归函数、跑测试。但真正要理解二叉树的题第一步不是刷题而是把树的“底层表示”搞清楚。树的节点在代码里长这样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) {} };每个节点有值和两个指针。理解这个结构最关键的一点是NULL或者说 nullptr也是树的一部分而不是错误。初学者写递归时最常见的梦魇就是“访问了空指针”本质上是没想清楚“当节点是空的时候我们的函数应该返回什么”。我在刷完整个专题后的体会是二叉树题目的解法和这个结构定义强相关你写的每一种遍历、每一段递归都是在这三个字段上做文章。1.2 我和代码随想录的二叉树学习顺序我自己一开始也走过弯路。先刷了 LeetCode 上各种二叉树随机题结果着实地一头雾水后来按照代码随想录的二叉树专题顺序重新学才把知识串起来。代码随想录的安排大致是这样二叉树的递归遍历前、中、后序二叉树的迭代遍历用栈模拟递归二叉树的层序遍历用队列广度优先求树的属性深度、节点数、平衡性、路径二叉树的修改与构造翻转、构建二叉搜索树性质、验证、增删查二叉树公共祖先、最终写到线索二叉树这个顺序不是随便排的。它遵循一条主线先学会遍历因为几乎所有二叉树题目都是遍历的变种然后通过遍历去“统计属性”接着通过属性去“构造/修改树”最后才是二叉搜索树这种带特殊性质的树。2. 二叉树的遍历递归、迭代与层序2.1 递归遍历的三要素我觉得比口诀更重要很多人记“前中后序”的口诀是“根左右、左根右、左右根”但只背口诀很容易出问题。真正写递归函数时要把握住三个要素递归函数的参数和返回值、终止条件、单层递归的逻辑。以中序遍历为例节点访问顺序是左子树→根→右子树void inorder(TreeNode* root, vectorint result) { if (root nullptr) return; inorder(root-left, result); // 左 result.push_back(root-val); // 根 inorder(root-right, result); // 右 }这个函数里参数是当前根节点和存放结果的数组终止条件是 root 为空单层逻辑就是把左子树、根、右子树按顺序处理。这里有一个关键点递归函数的返回值不是 void 也可以。比如求树的高度时返回 int搜索某个值时返回 TreeNode*。但无论返回什么终止条件永远要先想清楚。为什么终止条件是root nullptr因为叶子节点的左右孩子是空。递归到空节点时函数应该直接返回不能再访问 root-left否则就会因空指针而崩溃。这一点在处理“最小深度”时尤其重要后面我会详细讲。2.2 迭代遍历把递归栈显式化递归本质上是用函数调用栈。但如果树特别深递归可能导致栈溢出而且有些面试官就喜欢看你不用递归写遍历。迭代遍历的核心是用一个显式的栈来模拟递归过程。我以前觉得前序遍历的迭代很简单根节点入栈弹出后先右后左入栈这样出栈顺序就是根左右。代码vectorint preorderTraversal(TreeNode* root) { vectorint result; stackTreeNode* st; if (root ! nullptr) st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); result.push_back(node-val); if (node-right) st.push(node-right); if (node-left) st.push(node-left); } return result; }但中序和后序的迭代就没那么直观了。中序遍历需要沿着左子树一路走到最深处然后回头访问根再处理右子树。我之前没想通后来把代码随想录的“统一迭代法”看明白了才真正掌握。统一迭代法其实是用栈标记法入栈时给节点做个标记表示这个节点是否已经被访问过左右孩子。比如中序vectorint inorderTraversal(TreeNode* root) { vectorint result; stackTreeNode* st; if (root ! nullptr) st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); if (node ! nullptr) { if (node-right) st.push(node-right); // 右 st.push(node); // 中 st.push(nullptr); // 标记 if (node-left) st.push(node-left); // 左 } else { TreeNode* cur st.top(); st.pop(); result.push_back(cur-val); } } return result; }这里的 nullptr 标记就是“我已经将这个节点的左右孩子处理入栈了下次轮到它自己时直接输出”。我个人觉得统一迭代法虽然代码上多了几行但思想是真的统一前中后序都只是调整左右孩子和节点入栈的顺序而已不需要单独背三种迭代套路。2.3 层序遍历用队列解决“按层”问题层序遍历是二叉树的广度优先搜索几乎所有“按层统计”类题目比如每层平均值、每层最大值、锯齿形遍历都建立在它之上。核心是借助队列记录每一层的节点个数然后一口气把这一层全部处理完vectorvectorint levelOrder(TreeNode* root) { vectorvectorint result; queueTreeNode* que; if (root ! nullptr) que.push(root); while (!que.empty()) { int size que.size(); vectorint vec; for (int i 0; i size; i) { TreeNode* node que.front(); que.pop(); vec.push_back(node-val); if (node-left) que.push(node-left); if (node-right) que.push(node-right); } result.push_back(vec); } return result; }这里有几个很容易被初学者忽略的细节。第一int size que.size()必须在处理每一层前先固定因为 for 循环里会不断往队列里 push 新节点que.size() 会动态变化如果写成for (int i 0; i que.size(); i)就会导致每一层的处理次数变多或者变少。第二队列里存放的是节点指针判断左右孩子是否为空再入队空节点不能入队否则输出结果里会出现 nullptr 对应的默认值还容易引发后续访问错误。3. 二叉树的深度从递归公式到边界陷阱3.1 最大深度后序遍历求高度求二叉树的最大深度是面试题中出现频率最高的一类。这里的“深度”是从根节点到最远叶子节点的最长路径上的节点数。代码随想录给出的思路是树的最大深度等于根节点的高度而高度用后序遍历计算因为要先知道左右子树的高度才能算出本节点的高度。int maxDepth(TreeNode* root) { if (root nullptr) return 0; int leftDepth maxDepth(root-left); int rightDepth maxDepth(root-right); return max(leftDepth, rightDepth) 1; }这个递归为什么正确因为我们把问题拆成了当前树的高度 左子树高度和右子树高度的较大值 1。空树高度为 0所以递归的终止条件返回 0。很多人问为什么不能用前序遍历前序遍历是“从上往下”记录路径长度到叶子节点时更新结果其实也能做但是需要额外维护一个临时深度变量并且本质上不是“树的天然递归结构”代码写起来容易乱。3.2 最小深度一个容易出错的版本求最小深度时我第一次写出的代码是这样的int minDepth(TreeNode* root) { if (root nullptr) return 0; return min(minDepth(root-left), minDepth(root-right)) 1; }跑测试后发现完全错了。问题在于如果一个节点的左子树为空、右子树不为空最小深度应该由右子树决定而不是取 0 和右子树高度的最小值。比如一棵树只有根节点和右孩子1 \ 2正确的深度是 2但上面那个错误的写法会返回 1因为 min(0, 1) 1 1。原因是把“空子树”当成“最小深度为 0”参与了比较。但空子树并不是路径路径必须从根走到叶子节点。正确写法int minDepth(TreeNode* root) { if (root nullptr) return 0; if (root-left nullptr root-right nullptr) return 1; int min_depth INT_MAX; if (root-left ! nullptr) { min_depth min(min_depth, minDepth(root-left)); } if (root-right ! nullptr) { min_depth min(min_depth, minDepth(root-right)); } return min_depth 1; }这个 Case 我建议写二叉树代码的人都单独拿出来标记最小深度必须把“空子树”排除在计算之外。这个错误在 LeetCode 的提交里非常常见正是标题里“写二叉树程序时为什么总是报运行时错误”的经典来源之一。3.3 完全二叉树的节点数不只是遍历数数如果只是统计普通二叉树的节点数递归遍历一遍就可以了。但面试里经常会加大难度给一棵完全二叉树让你在优于 O(n) 的复杂度下统计节点数。这时要先理解完全二叉树的一个性质如果一棵子树是满二叉树那么它的节点数可以直接用2^h - 1算出h 是子树的高度。int countNodes(TreeNode* root) { if (root nullptr) return 0; TreeNode* left root-left; TreeNode* right root-right; int leftHeight 0, rightHeight 0; while (left) { left left-left; leftHeight; } while (right) { right right-right; rightHeight; } if (leftHeight rightHeight) { return (2 leftHeight) - 1; } return countNodes(root-left) countNodes(root-right) 1; }这段代码里的leftHeight和rightHeight分别表示从当前节点出发一路向左和一路向右的深度。如果两者相等说明这棵子树是满二叉树可以直接套公式不需要继续递归下去。这个方法在大量节点的完全二叉树上时间复杂度会明显优于逐个遍历。4. 写二叉树程序时为什么总是报运行时错误核心排查方向4.1 空指针解引用是头号杀手写二叉树程序时运行时错误Runtime Error绝大多数是空指针访问。为什么会空指针归纳下来主要有三类第一类直接访问了root-left而没有先判断root是否为空。比如if (root-left ! nullptr root-left-val target) { ... }这段代码的问题不在root-left而在于root本身就是空指针时root-left就已经是空指针解引用了。第二类递归终止条件不完整。比如求最小深度时如果不去判断左右孩子为空的情况就让minDepth(root-left)继续递归返回 0 再去参与比较逻辑上错了而如果连终止条件都漏了就会无限递归到栈溢出。第三类队列或栈中放入了空指针。我曾有一次在层序遍历时不判断左右孩子是否为空就直接入队结果队首节点是 nullptr后面访问node-val就崩溃了。4.2 递归没有收敛栈溢出与运行超时int badHeight(TreeNode* root) { return badHeight(root-left) 1; // 这么写完全错 }上面这种写法是错的因为递归函数压根没有终止条件。哪怕你加了if (root nullptr) return 0;也存在另一种情况递归函数里传的“下一层参数”没有向终止条件靠近。比如中序遍历时如果错误地把inorder(root, result)写成inorder(root, result)传成同一个节点那么递归就会在同一个节点上无限循环最终栈溢出。排查这类问题我自己的经验是三步走第一步检查递归函数的终止条件第二步确认每次递归传入的节点确实是当前节点的左右孩子第三步在关键位置打印节点的值观察递归是否按照预期的顺序收敛。4.3 数组越界隐藏在索引计算中二叉树相关的题目里还有一种运行时错误藏在“索引”里。比如用数组存二叉树时如果节点下标是 i那么左右孩子下标是 2i 和 2i1。当你对某个节点求孩子下标时如果没有判断下标是否小于数组长度就可能越界。我遇到过一道题需要从后序遍历和中序遍历构建二叉树递归时参数inLeft和inRight算错了导致数组下标为负编译器直接报 Segmentation Fault。这类错误调试起来很费时间建议在递归入口处先加一行断言校验传入参数是否合法。4.4 把调试信息打出来不要怕 print刷二叉树题时我养成了一个习惯在递归函数的入口处打印当前处理节点的值以及递归深度。比如void inorder(TreeNode* root, vectorint result, int depth 0) { if (root nullptr) return; for (int i 0; i depth; i) cout ; cout enter: root-val endl; inorder(root-left, result, depth 1); result.push_back(root-val); inorder(root-right, result, depth 1); }这样能看到递归的调用轨迹立刻就能发现是否访问了不该访问的节点或者在某个分支上递归层数异常增加。实测下来这个办法比单步调试高效得多尤其是针对“为什么总是报运行时错误”这类问题。5. 二叉搜索树从性质到增删查的完整落地5.1 验证二叉搜索树的经典陷阱二叉搜索树的定义要求左子树所有节点的值都小于根节点右子树所有节点的值都大于根节点。注意“所有”这两个字。很多人一开始会写出类似这样的代码bool isValidBST(TreeNode* root) { if (root nullptr) return true; if (root-left root-left-val root-val) return false; if (root-right root-right-val root-val) return false; return isValidBST(root-left) isValidBST(root-right); }这个写法在类似下面的结构上会出错5 / \ 4 6 / \ 3 7根节点 5 的右孩子 6 大于 5但 6 的左孩子 3 却小于 5这棵树不是 BST。上面代码中isValidBST(root-right)只检查了右子树内部是否满足“左小右大”检查到 3 和 7 时它认为 3 6 且 6 7 就通过了但完全没有考虑 3 和根节点 5 的大小关系。正确做法是给递归函数传一个区间min, max每个节点的值必须落在该区间内bool validate(TreeNode* node, long long minVal, long long maxVal) { if (node nullptr) return true; if (node-val minVal || node-val maxVal) return false; return validate(node-left, minVal, node-val) validate(node-right, node-val, maxVal); }用 long long 是因为测试数据里可能出现 INT_MIN 和 INT_MAX 作为节点值初始化的上下界需要用更宽的范围。5.2 搜索与插入并理解为什么可以用递归BST 的搜索和插入核心是充分利用有序性。搜索时如果目标值小于当前节点值只要去左子树找如果大于则去右子树找相等则返回。这一过程天然适合递归因为每次都能把搜索范围缩小一半。插入操作稍微绕一点但代码并不长TreeNode* insertIntoBST(TreeNode* root, int val) { if (root nullptr) { return new TreeNode(val); } if (val root-val) { root-left insertIntoBST(root-left, val); } else if (val root-val) { root-right insertIntoBST(root-right, val); } return root; }这里的关键思路是“递归的返回值来修改父节点的指针”。每当递归返回时就把子树的新根节点挂到父节点对应的一侧。如果插入的新节点正好落在叶子位置那么insertIntoBST(NULL, val)就会创建一个新节点返回层层挂接回去。很多刚学递归的人会困惑为什么不是单独写一个函数后手动修改指针因为在树的递归操作中“把递归函数的返回值赋值给当前节点的孩子指针”是一种标准模式它保证了树的结构在所有路径上都被正确维护。5.3 删除节点二叉树里最考验细心的地方删除 BST 节点需要分情况讨论这部分我学的时候也花了不少时间。大体归纳为四种情况要删除的节点是叶子节点直接置为空。要删除的节点只有左孩子用左孩子顶替它。要删除的节点只有右孩子用右孩子顶替它。要删除的节点既有左孩子又有右孩子找到右子树中最小的节点或者左子树中最大的节点用它来替换要删除的节点然后递归删除那个被替换的节点。对应代码TreeNode* deleteNode(TreeNode* root, int key) { if (root nullptr) return nullptr; if (key root-val) { root-left deleteNode(root-left, key); } else if (key root-val) { root-right deleteNode(root-right, key); } else { if (root-left nullptr) return root-right; if (root-right nullptr) return root-left; TreeNode* minNode root-right; while (minNode-left ! nullptr) { minNode minNode-left; } root-val minNode-val; root-right deleteNode(root-right, minNode-val); } return root; }这里最值得注意的坑是当节点既有左孩子又有右孩子时如果你直接选择用右子树的最小节点替换然后递归删除那个最小节点必须保证传入的起点是root-right而不是root否则可能把自己删除掉。我就在这个细节上吃过亏调试了半小时才从二叉树结构打印中发现最小节点被错误地替换了两次。5.4 中序遍历与 BST 的关系还有一个实战中高频的考点BST 的中序遍历结果是递增序列。这个性质可以用来解决“验证 BST”的另一种写法也可以用来做“ BST 中第 k 小元素”这类题。int kthSmallest(TreeNode* root, int k) { stackTreeNode* st; TreeNode* cur root; while (cur ! nullptr || !st.empty()) { while (cur ! nullptr) { st.push(cur); cur cur-left; } cur st.top(); st.pop(); k--; if (k 0) return cur-val; cur cur-right; } return -1; }这段代码就是用迭代中序遍历每弹出一个节点就把当前节点在有序序列中的位次减 1直到找到第 k 个。6. 线索二叉树把空闲指针“废物利用”6.1 线索二叉树要解决什么问题普通二叉树的每个节点都有左右指针但很多节点的左右指针是空的。统计下来一棵有 n 个节点的二叉树总共有 2n 个指针其中只有 n-1 个指针指向真实的孩子节点剩下的 n1 个指针是空指针。线索二叉树的基本思想就一句话把这些空指针利用起来让它们指向某种遍历顺序下的前驱节点或后继节点从而加快遍历速度避免反复使用栈或递归。从“代码随想录”的框架来看线索二叉树是二叉树专题的进阶内容。它在实际工程里的用途不像普通遍历那么普遍但在理解“二叉树存储结构”和“遍历的底层逻辑”方面很有价值。比如某些数据库索引、内存管理的实现借鉴了很多类似“线索化”的思路。6.2 线索化的核心实现前驱与后继线索二叉树在每个节点上增加了两个标志位ltag和rtag。如果ltag 0表示左指针指向左孩子如果ltag 1表示左指针指向前驱节点。右指针同理rtag 1时指向后继节点。实现中序遍历线索化最常见的方式是借助一个全局变量pre来记录上一个访问的节点struct ThreadNode { int val; ThreadNode *left, *right; bool ltag; bool rtag; }; void inorderThreaded(ThreadNode* cur, ThreadNode* pre) { if (cur nullptr) return; inorderThreaded(cur-left, pre); // 线索化左子树 if (cur-left nullptr) { cur-left pre; cur-ltag true; } if (pre ! nullptr pre-right nullptr) { pre-right cur; pre-rtag true; } pre cur; inorderThreaded(cur-right, pre); }这里有一个很关键的细节判断“是否为线索”时看的是标志位而不是指针是否为空。因为一旦线索化完成原来的空指针就变成了指向其它节点的指针如果继续按照空指针判断你就会一头雾水。6.3 线索化之后遍历的栈都不需要了线索化后中序遍历可以完全不用递归和栈只靠线索就能在 O(1) 空间下完成。首先找到最左下角的节点然后不断利用“后继线索”向右移动如果右指针不是线索就转向右子树并再次找到其最左节点。void inorderTraversalByThread(ThreadNode* root) { ThreadNode* cur root; while (cur-left ! nullptr cur-ltag false) { cur cur-left; } while (cur ! nullptr) { visit(cur); if (cur-rtag true) { cur cur-right; } else { cur cur-right; while (cur ! nullptr cur-ltag false) { cur cur-left; } } } }不过说实话我在实际刷题中用到的次数不多但它对理解“遍历的本质”很有帮助递归遍历依靠函数调用栈迭代遍历依靠显式栈而线索化遍历依靠的是“事先存储好的后继信息”。三种方案分别用不同的手段回答了同一个问题下一步该访问谁。7. 二叉树题型的实战心得与避坑清单7.1 从遍历类型反推题目解法刷了不少二叉树题之后我发现一个规律当你拿到一道二叉树题目先问自己“它需要用哪种遍历”。求深度的用后序遍历因为要先知道左右孩子的情况找路径的用前序遍历因为要沿着路径从根向下走层序相关的用队列搜索二叉树的验证可以借助中序遍历。把遍历方式和题目需求对应起来做题速度会有质的提升。7.2 递归函数设计先想三件事我在每次写递归前都会强制自己在注释里写下三行函数的参数里有什么返回值是什么终止条件是什么。这样做的好处是防止写着写着忘记边界。尤其是返回值的类型很多时候决定了题能不能做对。比如“判断是否平衡二叉树”递归函数返回 bool 当然也可以但如果既要返回是否平衡又要返回高度更优雅的方式是返回高度用特殊值 -1 表示不平衡int getHeight(TreeNode* root) { if (root nullptr) return 0; int left getHeight(root-left); if (left -1) return -1; int right getHeight(root-right); if (right -1) return -1; if (abs(left - right) 1) return -1; return max(left, right) 1; } bool isBalanced(TreeNode* root) { return getHeight(root) ! -1; }这种设计比返回 pair 更简洁也是我在代码随想录的题解里第一次看到并沿用至今的思路。7.3 二叉树调试三板斧作为一个踩过无数坑的人我把二叉树调试的经验总结为三板斧第一板斧打印树的结构。写一个递归打印函数把每个节点的值和左右孩子的值输出快速观察结构是否符合预期。第二板斧用最小用例测试。拿一棵只有两三个节点的树去跑边界条件远比直接上一棵复杂树有效。第三板斧在递归入口和出口各打印一次观察递归路径是否合理。这套方法帮我解决过很多“为什么总是报运行时错误”的问题尤其是空指针和递归不收敛这两类。