★ FEATURED ARTICLE 1. 从“为什么需要两种存储”开始理解二叉树1.1 数组和链式存储的本质差异连续与离散二叉树在面试和实际项目中出现的频率有多高不用我多说。但很多人学二叉树一上来就背“前序遍历、中序遍历、后序遍历”背完就忘遇到手撕代码还是慌。原因很简单没有先理解存储方式这个底层问题。先想一个最基础的问题一棵二叉树在内存里到底怎么放答案只有两种思路。第一种是连续内存也就是用数组按照某种规律把节点排在一个线性表里第二种是离散内存也就是用节点加指针把父子关系通过地址串起来。前者叫顺序存储后者叫链式存储。两者的核心差别不是“谁更高级”而是“连续 vs 离散”这一对根本矛盾。数组存储的特点是内存连续、按下标随机访问 O(1)、不需要额外指针空间但插入和删除节点往往要移动大量数据而且如果树形稀疏会浪费大量空间。链式存储的特点是动态分配、天然支持任意形态的树、增删节点只改指针但每个节点都要多存两个指针字段缓存局部性也不如连续内存。把这个搞明白你再看后面所有的代码实现就不会觉得是死记硬背而是顺着“这个场景适合哪种存储”的推导自然展开。1.2 二叉树为什么不能每种场景都用同一种存储实际开发里这两种方式各有各的主场。数组存储最常见的地方是堆Heap和优先队列。堆要求是一个完全二叉树节点按层序排列非常紧凑数组下标天然能表达父子关系用数组实现堆效率极高这也是标准库优先队列的底层原理。又比如某些线段树、树状数组的实现底层就是数组利用连续内存的随机访问优势。链式存储则更通用。普通的二叉搜索树、表达式树、文件系统目录树形态千奇百怪有的左子树很深有的右子树很空用数组去存很可能出现“树只有 5 个节点数组却要开 2 的 5 次方大小”的尴尬。链式结构没有这个问题节点有多少指针就分配多少空间和树的真实形态严格成正比。所以学习二叉树存储方式本质上是在学一种“空间换时间、还是时间换空间”的工程取舍。一个合格的后端开发者不会在维护一棵动态变化的树时强行用数组一个刷过 LeetCode 的面试者也不该在实现堆排序时非要用链表。两种存储方式都掌握你才能在面对具体问题时快速判断。2. 顺序存储细节数组下标里的父子关系怎么算2.1 堆式下标的推导与边界条件顺序存储的核心是“用下标位置代替指针”。假设树根放在数组下标 0 的位置那么对任意下标为 i 的节点左孩子下标2i 1右孩子下标2i 2父节点下标(i - 1) / 2这个公式是怎么来的你在一棵完全二叉树里按层序遍历的顺序从 0 开始编号第 0 层有 1 个节点第 1 层有 2 个第 2 层有 4 个。第 k 层节点从第 2^k - 1 个下标开始第 k 层第 j 个节点的下标是 (2^k - 1) j。它的左孩子在第 k1 层位置是 2j所以左孩子下标是 (2^(k1) - 1) 2j 2 * ((2^k - 1) j) 1 2i 1。右孩子自然就是 2i 2。所以只要给你一个数组下标你就能在 O(1) 时间内算出它的父亲和两个孩子。这就是顺序存储最大的价值不需要指针不需要递归找父节点一个除法、一个乘法全搞定。要注意边界条件。数组下标从 0 开始算很多 C/C 初学者容易和从 1 开始的习惯搞混。如果采用下标从 1 开始的设计规则变为左孩子 2i、右孩子 2i1、父节点 i/2这常见于一些算法竞赛的实现。两种规则都没问题但代码里必须统一不能在同一个函数里一会儿用 0 基一会儿用 1 基。2.2 什么时候选数组存储满二叉树与完全二叉树数组存储并不是所有二叉树都能高效承载。假设一棵二叉树只有 5 个节点但形态是一条向右的链根、右孩子、右孩子的右孩子、右孩子的右孩子的右孩子……这种情况下如果套用顺序存储右孩子下标是 2022下一层是 2226再下一层是 14再下一层是 30。5 个节点要占用下标 0、2、6、14、30数组长度需要至少 31空间浪费超过 80%。更极端的例子如果树高为 31只有一条右链那数组需要开 2^31 大小这在普通开发环境里基本是不可接受的。所以顺序存储只有在“完全二叉树”或“接近完全二叉树”的场景下才有优势。反过来满二叉树和完全二叉树用数组存储非常完美没有空洞每个下标都被利用父子关系计算稳定缓存命中率也高。这也是堆为什么必须用完全二叉树的原因——它让数组存储的数学关系完全成立不会出现空间爆炸。实际工程中当你拿到一个问题先判断形态如果树的插入、删除非常频繁或者树形稀疏不定优先链式如果数据量基本固定、形态接近完全二叉树优先数组。这个判断不是靠感觉而是靠上面这种空间利用率的推算。3. 链式存储细节节点、指针与动态创建3.1 节点结构体与内存布局链式存储的实现很直白每个节点包含一个数据域和两个指针域。用 C 表示就是struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };这里每个节点在堆上独立分配。一个二叉树节点通常需要 16 字节左右的内存其中 4 字节存 int8 字节存左指针8 字节存右指针算上内存对齐可能更多。链式结构能表达任意树形完全树、稀疏树、斜树、甚至空树都没有问题。我自己的习惯是写二叉树代码时坚持构造节点必须用 new释放节点必须用 delete不能混着来。有些教程为了图方便直接 return new TreeNode(x)看起来简洁但在工程代码里资源所有权不清晰后期很容易泄漏。项目里见过最头疼的问题是树销毁时只 delete 根节点子节点全部泄漏内存越涨越高定位半天才发现是析构逻辑漏了子树。3.2 数组转链式、链式转数组的实操方法知道两种存储方式还不够还要会互相转换。面试里常见的题目是给你一个按堆式下标排列的数组让你还原成二叉树或者反过来给你一棵二叉树让你输出它的顺序存储数组。数组转链式非常简单利用递归和下标关系TreeNode* buildFromArray(const vectorint arr, int idx) { if (idx arr.size() || arr[idx] -1) return nullptr; TreeNode* node new TreeNode(arr[idx]); node-left buildFromArray(arr, 2 * idx 1); node-right buildFromArray(arr, 2 * idx 2); return node; }注意这里的 -1 表示空节点这是顺序存储里常用的占位符。但如果题目里真实节点值本身就有 -1就需要额外约定。我在项目里一般习惯用 INT_MIN 或者单独做一个 bool 数组标记空位避免和真实数据冲突。链式转数组稍微麻烦一点。你需要在递归过程中给每个节点分配下标然后填数组void flattenToArray(TreeNode* node, int idx, vectorint arr) { if (!node) return; if (idx (int)arr.size()) arr.resize(idx 1, -1); arr[idx] node-val; flattenToArray(node-left, 2 * idx 1, arr); flattenToArray(node-right, 2 * idx 2, arr); }这里的关键是递归前先把数组扩充到足够大小否则填 idx 位置时可能越界。很多新手写这段代码时直接用 arr[idx] node-val然后崩溃在数组访问越界上原因就是没有先 resize。别小看这几行代码转换逻辑一旦写错数据错位很难排查。4. 完整代码实现五种遍历与序列化一次拿捏4.1 基础结构与递归遍历先序、中序、后序终于到代码实现环节。我会从最常用的递归遍历开始这种代码最直观也最不容易把人的思路带偏。下面是一个可以直接编译运行的完整示例#include iostream #include vector #include stack #include queue #include string #include sstream using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; // 递归先序 void preorder(TreeNode* root, vectorint res) { if (!root) return; res.push_back(root-val); preorder(root-left, res); preorder(root-right, res); } // 递归中序 void inorder(TreeNode* root, vectorint res) { if (!root) return; inorder(root-left, res); res.push_back(root-val); inorder(root-right, res); } // 递归后序 void postorder(TreeNode* root, vectorint res) { if (!root) return; postorder(root-left, res); postorder(root-right, res); res.push_back(root-val); } int main() { // 构造一棵示例二叉树 // 1 // / \ // 2 3 // / \ \ // 4 5 6 TreeNode* root new TreeNode(1); root-left new TreeNode(2); root-right new TreeNode(3); root-left-left new TreeNode(4); root-left-right new TreeNode(5); root-right-right new TreeNode(6); vectorint res; preorder(root, res); for (int v : res) cout v ; // 1 2 4 5 3 6 cout endl; res.clear(); inorder(root, res); for (int v : res) cout v ; // 4 2 5 1 3 6 cout endl; res.clear(); postorder(root, res); for (int v : res) cout v ; // 4 5 2 6 3 1 cout endl; return 0; }递归遍历的规律非常清晰先序是“根左右”中序是“左根右”后序是“左右根”。做题的时候判断某个序列是什么遍历你就看根节点出现在前面、中间还是后面。出现前面的是先序中间的是中序后面的是后序。递归实现的优点是代码短、可读性强缺点是当树深度非常大时递归栈可能溢出。C 默认栈空间在 Linux 上通常是 8MB一个节点压栈几十字节当树高度达到几万层时就会爆栈。生产环境如果确定树高不大递归没问题否则就要考虑迭代写法。4.2 迭代遍历用栈实现前中后序迭代遍历是面试高频题。很多人只知道递归一要求“不用递归写一遍”就卡住。其实核心思想就一句话用栈模拟系统函数调用栈。先序迭代最直白。先访问根把右孩子入栈再把左孩子入栈。为什么先右后左因为栈是后进先出先入栈的右孩子会被后处理左孩子反而先出栈满足“根左右”的顺序。vectorint preorderIterative(TreeNode* root) { vectorint res; if (!root) return res; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* cur st.top(); st.pop(); res.push_back(cur-val); if (cur-right) st.push(cur-right); if (cur-left) st.push(cur-left); } return res; }中序迭代稍微绕一点。思路是从根开始一路把左孩子压栈直到左孩子为空然后弹出栈顶访问再转向右子树。这个过程用代码表达就是vectorint inorderIterative(TreeNode* root) { vectorint res; stackTreeNode* st; TreeNode* cur root; while (cur || !st.empty()) { while (cur) { st.push(cur); cur cur-left; } cur st.top(); st.pop(); res.push_back(cur-val); cur cur-right; } return res; }后序迭代最容易被问因为它最反直觉。这里分享一个我自己常用的技巧不需要硬记复杂的单栈实现直接用两个栈。先按“根右左”的顺序遍历然后反转结果就是“左右根”。我在面试中手写后序遍历时一直用这个双栈方案思路清晰、不容易出错vectorint postorderIterative(TreeNode* root) { vectorint res; if (!root) return res; stackTreeNode* st1, st2; st1.push(root); while (!st1.empty()) { TreeNode* cur st1.top(); st1.pop(); st2.push(cur); if (cur-left) st1.push(cur-left); if (cur-right) st1.push(cur-right); } while (!st2.empty()) { res.push_back(st2.top()-val); st2.pop(); } return res; }这个技巧理解起来很简单st1 先序遍历时我们把“根右左”搞出来存到 st2 里最后 st2 全部弹出顺序自然逆转成“左右根”。代价是额外 O(n) 的栈空间但大多数场景完全值得。至于那个只用单栈实现后序的写法性能上省不了太多反而容易把自己绕晕我不建议新手一上来就啃。4.3 层序遍历与重建为数组存储层序遍历是另一种重要遍历方式它天然对应“顺序存储”的数组下标顺序。实现用队列这才是真正的“广度优先”。vectorint levelOrder(TreeNode* root) { vectorint res; if (!root) return res; queueTreeNode* q; q.push(root); while (!q.empty()) { TreeNode* cur q.front(); q.pop(); res.push_back(cur-val); if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } return res; }层序遍历的价值在于它输出的节点顺序恰好是顺序存储时数组从下标 0 开始的排布顺序。所以你完全可以用层序遍历作为“链式转数组”的桥梁。上面的levelOrder只收集了值如果还要保留空节点位置就需要在遍历时标记空位。实际操作里我会额外用一个 bool 数组存“是否为空”或者直接给定一个不可能出现的占位值避免丢失树的形状信息。树转数组的完整写法我前面已经给出下面补一个数组转树的调用示例顺便演示两者如何配合// 链式 - 顺序 void flattenToArray(TreeNode* node, int idx, vectorint arr) { if (!node) return; if (idx (int)arr.size()) arr.resize(idx 1, -1); arr[idx] node-val; flattenToArray(node-left, 2 * idx 1, arr); flattenToArray(node-right, 2 * idx 2, arr); } vectorint treeToArray(TreeNode* root) { vectorint arr; flattenToArray(root, 0, arr); return arr; } // 顺序 - 链式 TreeNode* arrayToTree(const vectorint arr, int idx) { if (idx (int)arr.size() || arr[idx] -1) return nullptr; TreeNode* node new TreeNode(arr[idx]); node-left arrayToTree(arr, 2 * idx 1); node-right arrayToTree(arr, 2 * idx 2); return node; }这里有个很实用的工程经验如果数组代表的是一棵稀疏树flattenToArray会自动 resize 到最大下标中间位置补 -1。但如果你面对的是一个巨大的稀疏树这个过程会开辟非常大的数组可能直接内存溢出。所以链式转数组之前最好先计算树高估一下下标上界。如果树高超过 30基本可以放弃数组存储了这在 2.2 节已经说过。4.4 二叉树的序列化与反序列化面试里还有一种绕不开的题给定一棵二叉树把它变成一个字符串再从这个字符串还原出完全一样的树。LeetCode 上叫“二叉树的序列化与反序列化”其实本质就是“自定义格式 先序遍历”。我的序列化策略是用先序遍历遇到空节点写一个#节点和节点之间用空格分隔。这样字符串既能表达数字又能表达空指针。void serializeHelper(TreeNode* node, ostringstream out) { if (!node) { out # ; return; } out node-val ; serializeHelper(node-left, out); serializeHelper(node-right, out); } string serialize(TreeNode* root) { ostringstream out; serializeHelper(root, out); return out.str(); } TreeNode* deserializeHelper(istringstream in) { string token; if (!(in token)) return nullptr; if (token #) return nullptr; TreeNode* node new TreeNode(stoi(token)); node-left deserializeHelper(in); node-right deserializeHelper(in); return node; } TreeNode* deserialize(const string data) { istringstream in(data); return deserializeHelper(in); }序列化时要注意一个坑别省略空节点。很多人第一次写序列化只把非空节点写进字符串比如树1 - 2和树1 - 右孩子2序列化结果完全一样反序列化时根本无法区分。空节点#不是可有可无的装饰它是树形结构的骨架。只要空节点位置写清楚任意形态的二叉树都能无损还原。另一坑是字符串流读取istringstream默认以空格分隔所以序列化时每个值后面必须跟一个空格。如果忘了加空格token 就会粘在一起stoi 解析直接报错或者解析出错误数字。我每次写这类代码开完ostringstream后第一件事就是确认输出格式里有没有空格。5. 常见问题与排查实录5.1 新手最容易踩的四个坑第一个坑空指针判断不到位。递归函数开头不写if (!root) return或者写完条件分支后忘记处理空节点导致访问node-val时崩溃。调试的时候报 not null 的错绕了一整圈回头一看漏了if (cur-left) q.push(cur-left)里的判空。第二个坑迭代遍历的入栈顺序记反。先序遍历需要先压右再压左这个和直觉相反非常容易写反。一个简单的自检方法拿一棵只有 3 个节点的树根为 1左孩子 2右孩子 3手动跑一遍你的循环。如果输出不是“1 2 3”就说明压栈顺序反了。第三个坑顺序存储时数组下标越界。链式转数组时递归到深层节点下标可能已经大于当前数组 size。我在项目里见过不止一次为了省一次 resize 判断直接arr[idx] value结果崩得莫名其妙。顺序存储的代码凡是用下标写入的地方必须先确认数组长度。第四个坑用-1表示空节点但真实数据里也存在 -1。这样反序列化时会把一个合法节点当成空节点丢掉。解决方法是序列化前约定一个值作为空节点标记并且保证该值不出现在数据里如果无法保证就用单独一个 bool 数组或自定义结构体来标记空位。这个坑在最开始设计数据结构时就要想清楚。5.2 高频问题速查表问题现象可能原因排查与解决方法递归遍历大树时程序崩溃递归深度过大系统栈溢出改用迭代遍历或用非递归方式实现层序遍历结果少了一些节点入队前没判空导致空节点也入队检查左右孩子入队时是否加了判空先序迭代输出顺序错乱压栈顺序反了应该先压右再压左手动跑一个三层小树验证顺序数组转链式后树形不对下标公式用错0基和1基混用统一使用 2i1 / 2i2 或 2i / 2i1不要混序列化字符串无法还原空节点没有写入占位符序列化时遇到 null 必须输出#数组存储时内存爆掉稀疏树强行用数组存储先算树高树高过大时改用链式存储反序列化出现随机值字符串流读取时没有空格分割每次写值后加空格读取用in token5.3 一个我常用的自测方法这里分享一个个人习惯拿到任何二叉树题目先构造一棵“破坏性”的测试树——让某个节点只有左孩子、某个节点只有右孩子、再有一个节点的子节点全部为空。然后用这棵树跑你先序、中序、后序、层序、序列化、反序列化全套流程。这样做的原因是只有左右子树不对称、有空节点穿插的树才能暴露出下标计算错误、判空遗漏、序列化缺#等一堆问题。如果只用一棵完全二叉树测试很多 bug 会被完美掩盖因为完全二叉树每个节点都有两个孩子空指针判断几乎不会触发。面试前或者手写代码完成后用这种畸形树快速过一遍基本能拦截掉七八成常见失误。另外一个工程上的建议写完树的销毁函数。C 里new出来的节点不会自动回收项目做完后要逐个delete。正确的二叉树析构依然用递归void deleteTree(TreeNode* root) { if (!root) return; deleteTree(root-left); deleteTree(root-right); delete root; }先删孩子再删自己。如果先删自己再删孩子后面对指针访问已经是悬垂指针行为未定义。平时写 demo 可能无所谓但做长驻服务或者企业项目时内存泄漏是会被严格审查的。我个人在实际操作中的体会是二叉树的存储方式不是一个孤立的知识点它串起了数组、链表、递归、栈、队列这一整条数据结构的线。每次我遇到树相关的需求都会先问自己三句话这棵树形态是稳定的吗它需要频繁增删节点吗我下一步要对它做什么操作三个问题想完用数组还是用链式基本就清楚了。代码写多了你会发现真正困难的工作不是实现而是选择在哪一种结构上实现。
阅读完成 · 觉得有帮助？
