《算法五树 Trees V2》是算法系列笔记的第五篇。这篇标题里加个V2是因为去年我写过一份树的学习总结当时把概念、遍历模板、代码一股脑贴上去后来回看发现全是“正确的废话”——定义背下来了题也刷了但遇到稍微变形的题目还是会卡。今年又花时间把树重新梳理了一遍同时接触了设备树、B树、哈夫曼编码这些真实工程场景才意识到树不是拿来背的它是理解递归、搜索、缓存、编译、压缩等等一堆问题的共同底座。这篇文章就是重学之后的笔记主题很集中树到底是什么、为什么递归和树绑定得这么紧、遍历有哪些花活、二叉搜索树为什么会退化、实际开发里那些“特殊树”都在解决什么问题。适合正在学数据结构与算法的人也适合工作几年后想回炉补基础的朋友。1. 树的本质为什么很多问题最终都被建模成树1.1 从“无环连通图”到递归定义数据结构教材给树的定义通常有两套。一套是集合式定义树是n个节点的有限集合要么为空要么有且仅有一个根节点并且除根节点外其余节点可以分成m个互不相交的有限集合每个集合本身又是一棵树。另一套是图论视角树是无环连通图。这两套定义都正确但对初学者来说真正能指导写代码的其实是递归定义。你可以这样理解一棵树要么是空要么由一个根节点和若干棵互不相交的子树组成而每一棵子树又是更小的树子树的子树还满足同样的结构直到没有孩子为止。这个递归定义直接告诉了我们递归函数怎么写。写树的递归算法不需要在一开始就考虑整棵树的规模只需要回答三个问题当前节点要做什么。左子树递归返回的结果怎么用。右子树递归返回的结果怎么用。最典型的例子是求树的高度。树的高度等于1 max(左子树高度, 右子树高度)空树高度是0。这个结论不是靠记忆而是从树的递归定义直接推出来的。你理解了这层再去看后续的所有树形DP问题套路都会清晰很多。用一个生活化的比喻公司组织架构就是一棵树。CEO是根节点没有父节点普通员工通常是叶子节点没有孩子部门经理是内部节点既有上级又有下级。如果某天出现了一个人同时向两个主管汇报的情况那就不再是树而是一张图因为出现了环。树强调的正是“有层级、无环、可递归”。1.2 树在工程世界里的真实存在很多人觉得树只是面试题里的东西其实工程里树无处不在。文件系统从根目录出发每一层目录是内部节点文件是叶子节点。你在终端里不断cd切换路径本质就是在树上走路径。浏览器DOMHTML标签层层嵌套JavaScript操作DOM就是在遍历和修改一棵树。编译器解析源代码后生成抽象语法树AST语法检查、类型推导、代码优化和代码生成都发生在这棵树上。数据库索引MySQL InnoDB底层用B树Redis虽然主要用哈希但在需要范围查询的场景里也会引入有序结构。网络路由IP最长前缀匹配可以借助字典树实现下一跳查表本质上是树的查找。这些场景之所以都选择树结构是因为它们都存在“一对多”的归属关系一个父节点下面有多个子节点每个子节点又可以继续往下分出多个。这种关系用数组表达不自然用链表表达也需要大量额外的指针来维护“层级”而树作为天然的分层结构能把任意递归分解的问题都装进去。1.3 树最大的价值是让复杂度从 O(n) 变成 O(log n)数组和链表都是线性结构数据再多也只是一条线找某个值只能从头到尾扫一遍平均复杂度O(n)。树引入了一个“决策”过程在二叉搜索树里每次比较大小都能决定是往左还是往右相当于每次把搜索空间砍掉一半。这就是二分思想的来源。归并排序的递归过程画出来是一棵倒着的树二分查找的比较过程也是一棵二叉决策树甚至机器学习里的决策树算法本质就是通过一系列条件判断完成分类。所以学树学的不仅是一堆术语更是一种“通过分层比较降低工作量”的思维模式。从这一点出发你再去看后面所有围绕树的优化方案都会发现大家想尽办法在做一件事控制树的高度。树的高度越矮搜索路径越短操作效率越高。AVL、红黑树、B树、B树本质上都是围绕“如何把高度压住”在做文章。2. 先把“深度”“高度”“度”这些概念钉死2.1 节点之间的关系词别再把深度和高度弄反树里的称呼很多根节点、叶子节点、内部节点、父节点、子节点、兄弟节点、祖先、后代。这些理解起来不难真正容易混淆的是深度、高度和层数。我的记忆口诀是深度是从根往下数高度是从叶子往上数。根节点的深度是0叶子节点的高度是0。层数一般从1开始数根节点是第1层。但很多教材和题目对起点规定不同比如有的题目说“根节点深度为1”有的说“空节点高度为0”这就容易导致边界判断差一个。举一个具体例子一棵只有一个根节点的树它的深度是0高度也是0。如果根节点带一个孩子根节点的深度仍然是0但根节点的“高度”变成1孩子的深度是1孩子的高度是0。我见过很多人在算树的深度时直接把“从根到最远叶子经过的节点数”当成答案那单节点树就是1如果按边数理解答案就是0。两种说法都不算错问题是必须全程保持一致否则写出来的代码经常会出现差一错误。2.2 树的存储链式存储、数组存储和两个变体最通用的存储方式是链式存储每个节点保存数据值和指向孩子的指针。二叉树只需要左右两个指针多叉树可以用一个孩子数组保存。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right链式存储虽然直观但有两个问题一是每个节点都要额外存指针内存开销不小二是节点在内存里离散分布遍历时缓存命中率不如连续数组高。所以对于完全二叉树这类结构用数组存储更合适。根节点放在下标1那么下标i的节点左孩子下标是2*i右孩子下标是2*i1父节点下标是i//2。这个编号规则在堆排序和线段树里非常常用一定要记牢。工程里还会出现两种存储变体。第一种是父指针表示法每个节点只保存父节点的下标或指针适合需要频繁向上回溯祖先的场景并查集就是这么实现的。第二种是孩子兄弟表示法把普通树的第一个孩子当作left下一个兄弟当作right硬是把任意多叉树转成二叉树这样就能复用所有二叉树算法。看懂这两种变体之后你对“树怎么存”的认知就不会局限于链表那一套。2.3 树的形态分类先用一张表记住主干树的形态核心约束典型用途二叉树每个节点最多两个孩子基础形态进一步细分满二叉树每一层都塞满节点理论模型完全二叉树除最后一层外全满最后一层从左到右连续堆的底层存储二叉搜索树左子树值小于根右子树值大于根查找、有序集合平衡二叉树任意节点左右子树高度差不超过1防止查找退化多叉树/B树一个节点可存多个关键字和多个孩子文件系统、数据库索引字典树字符分布在路径上节点表示前缀前缀匹配、自动补全哈夫曼树带权路径长度最小压缩编码、最优判定不要被这么多形态吓到它们之间其实是一条演进链。二叉树最简单但普通二叉树可能退化成链表于是加上有序性变成二叉搜索树又为了防止有序插入时退化加上平衡约束变成AVL或红黑树当数据量大到内存放不下为了减少磁盘IO又演化出多叉的B树家族。所有变化都围绕“查找效率”和“存储成本”这两个维度在权衡。把这条演进链记在脑子里比逐个背诵定义有用得多。3. 遍历递归栈与队列这场好戏3.1 深度优先的前序、中序、后序一套模板吃透遍历是树章节绕不开的核心。深度优先遍历本质是处理“根、左、右”的相对顺序只是输出根节点的时机不同前序根左右适合复制树结构。中序左根右在二叉搜索树上会得到有序序列。后序左右根适合先处理完孩子再处理父节点的场景例如释放内存、统计子树信息。递归代码几乎是一套模板def preorder(root): if not root: return [] return [root.val] preorder(root.left) preorder(root.right) def inorder(root): if not root: return [] return inorder(root.left) [root.val] inorder(root.right) def postorder(root): if not root: return [] return postorder(root.left) postorder(root.right) [root.val]这段代码可读性很高但每次递归都会新建列表性能一般工程里通常会用一个result列表收集结果。作为理解DFS的入口递归模板是最好的起点因为它直接对应树的递归定义。这里要特别说一下中序。很多初学者不理解为什么“中序遍历二叉搜索树”会得到有序序列。原因很简单BST保证左子树所有节点值都小于根右子树所有节点值都大于根中序按照“左根右”的顺序访问自然就把节点值从小到大排列出来。这个结论在很多BST题目里都是起手式。3.2 层序遍历队列的经典应用层序遍历也叫广度优先遍历BFS它不用递归而是用队列。逻辑是先把根节点入队然后每次弹出队首节点再把它的左孩子和右孩子依次入队。队列的先进先出特性恰好让同一层的节点按顺序被处理。如果题目要求按层输出结果可以在每一层开始前先量一下当前队列长度一次性把当前层的节点全部弹出来from collections import deque def level_order(root): if not root: return [] q, result deque([root]), [] while q: level_vals [] for _ in range(len(q)): node q.popleft() level_vals.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) result.append(level_vals) return result这里有一个关键细节len(q)必须在循环前固定住因为循环过程中会不断往队列尾部加入新节点队列长度是变化的。第一次写层序遍历的人很容易在这里踩坑导致把下一层节点也带进当前层的输出。3.3 之字形遍历层序遍历的小改版之字形遍历也叫锯齿形遍历是层序遍历的进阶变体要求奇数层从左往右偶数层从右往左。实现方式有两种一种是拿到整层结果后根据层号决定要不要反转另一种是使用双端队列在头部或尾部插入省掉反转操作。def zigzag_level_order(root): if not root: return [] q, result, left_to_right deque([root]), [], True while q: level_vals deque() for _ in range(len(q)): node q.popleft() if left_to_right: level_vals.append(node.val) else: level_vals.appendleft(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) result.append(list(level_vals)) left_to_right not left_to_right return result核心思路不是真的把遍历顺序改掉而是控制“往结果里放数据”的方向。这样所有节点的入队顺序完全统一代码逻辑好维护。面试里很多衍生题比如按层输出、按列输出、右视图都是在这个基础上加一点变化。3.4 从前序中序重建二叉树遍历不只是输出顺序它本身就是还原树的线索。给定前序和中序遍历序列可以唯一重建一棵二叉树。原理其实不复杂前序序列的第一个元素一定是根找到这个根在中序序列里的位置左边就是左子树的中序序列右边就是右子树的中序序列再根据左右子树的长度把前序序列切成对应的左右子树前序序列递归下去就能完成建树。def build_tree(preorder, inorder): index {val: i for i, val in enumerate(inorder)} def helper(pre_l, pre_r, in_l, in_r): if pre_l pre_r: return None root_val preorder[pre_l] root TreeNode(root_val) pos index[root_val] left_size pos - in_l root.left helper(pre_l 1, pre_l left_size, in_l, pos - 1) root.right helper(pre_l left_size 1, pre_r, pos 1, in_r) return root return helper(0, len(preorder) - 1, 0, len(inorder) - 1)这个代码最繁琐的是下标计算。每写一次我都建议用一个非常小的例子手算一遍比如前序[3,9,20,15,7]和中序[9,3,15,20,7]把每一层递归的边界写出来跑通之后你会发现所有下标都是对称且有规律的下次再写就不容易错。4. 二叉搜索树查找、删除和平衡的连锁反应4.1 BST的查找与插入逻辑BST通过值的大小关系把搜索空间一分为二。查找时如果目标小于当前节点值去左子树找如果大于去右子树找如果等于说明找到。每走一步都丢掉一半的候选节点平均时间复杂度O(log n)。插入逻辑类似从根节点开始比较一直找到空位置把新节点挂上去。这里有个细节容易出问题BST允许重复值时的处理方式并不统一。有的实现把重复值放在右子树有的约定“小于等于”走左子树。LeetCode这一类的在线题目通常不会把重复值设计得太复杂但像TreeMap或者std::map这类实现对重复键的处理都是直接覆盖或者拒绝插入。写代码之前最好先想清楚题目是否允许重复否则删除和查找的边界会对不上。4.2 删除操作为什么麻烦删除节点是BST的经典难点三种情况的分析几乎是面试固定题型被删节点是叶子直接删除父节点对应孩子置空。被删节点只有一个孩子把孩子顶上来替换被删节点。被删节点有两个孩子找一个合适的替代者通常是左子树的最大值或右子树的最小值把它的值复制到当前节点然后递归删除那个替代者。这种情况之所以选左子树的最大值或右子树的最小值是因为它们都满足一个条件除了被拿走的节点外原树仍然保持BST的大小关系。用右子树最小值替换根节点那么根节点的值仍然小于右子树所有节点、大于左子树所有节点BST性质不被破坏。def delete_node(root, key): if not root: return None if key root.val: root.left delete_node(root.left, key) elif key root.val: root.right delete_node(root.right, key) else: if not root.left: return root.right if not root.right: return root.left # 找右子树最小节点 min_node root.right while min_node.left: min_node min_node.left root.val min_node.val root.right delete_node(root.right, min_node.val) return root这个代码里最需要小心的是第二种情况下直接return root.right或return root.left。很多人在纸上画得出来但写代码时容易忘记把返回值接到父节点上。你要理解递归函数每一层返回的其实是“以当前节点为根的树在删除后的新根”这样整个链条才对得上。4.3 普通BST的退化问题从平衡到红黑树普通BST有一个致命问题如果插入的数据本身接近有序比如依次插入1、2、3、4、5BST会退化成一条链表查找复杂度变成O(n)。正因如此才有了各种自平衡方案。AVL树严格限制任意节点的左右子树高度差不超过1。它能保证很稳定的O(log n)查找但插入和删除时经常需要旋转代价比较大。红黑树用节点颜Se和若干条性质来约束左右子树的“黑高”平衡旋转次数比AVL少插入删除整体性能更好。Java的TreeMap、C的std::map底层都是红黑树没有用AVL关键就是因为红黑树的调整成本更低。B树/B树不是二叉树而是平衡多叉树一个节点能放多个关键字。这让树的高度变得更矮在磁盘IO昂贵的前提下B树家族明显更香。4.4 为什么数据库选B树而不是红黑树这是一个经常被问到的工程题。既然红黑树在内存里也能维持O(log n)查找为什么数据库不用它因为内存访问和磁盘访问的代价差了好几个数量级。B树的一个节点能存储很多个关键字整棵树的高度被压得很低一次主键查找往往只需要2到4次磁盘IO。如果用红黑树虽然复杂度也是O(log n)但log的底是2树高往往接近几十层磁盘IO次数会明显增加。另外B树所有数据都存在叶子节点并且叶子节点之间用链表串起来范围查询只需要沿着链表顺序读一遍。红黑树要做范围遍历就必须中序遍历并频繁回溯父节点在磁盘场景下代价更高。选B树不是因为它“更快”而是因为它更懂磁盘的脾气。5. 特殊树全家桶Trie、堆、哈夫曼树、表达式树5.1 堆一种用数组实现的完全二叉树堆不是“用来查找”的树而是一种基于完全二叉树的优先队列实现。最大堆保证父节点不小于孩子最小堆保证父节点不大于孩子。堆的插入和删除堆顶都是O(log n)取极值则是O(1)。堆排序利用的就是堆的这个性质不断删除堆顶就能得到全局有序序列复杂度稳定O(n log n)。工程里更常见的是把堆当作优先队列使用比如任务调度、求Top K、合并多个有序链表、求中位数。它的底层一般就是一个数组不需要存指针所以内存非常紧凑。5.2 字典树Trie把字符串存在路径上Trie和普通树最大的区别是节点不直接保存整个字符串而是把字符拆到边上。插入单词时从根节点出发逐个字符检查子节点是否存在不存在就创建全部字符处理完后在最后一个节点打上结束标记。class TrieNode: def __init__(self): self.children {} self.is_end False class Trie: def __init__(self): self.root TrieNode() def insert(self, word): node self.root for ch in word: if ch not in node.children: node.children[ch] TrieNode() node node.children[ch] node.is_end True def search(self, word): node self.root for ch in word: if ch not in node.children: return False node node.children[ch] return node.is_end def starts_with(self, prefix): node self.root for ch in prefix: if ch not in node.children: return False node node.children[ch] return TrueTrie有两个优势一是查询时间只跟字符串长度有关跟字典里存储的单词数量无关二是天然支持前缀匹配。搜索引擎自动补全、输入法词频统计、IP路由最长前缀匹配都是典型应用。代价是每个节点都需要存一个孩子指针集合空间消耗比较大工程里经常用数组或哈希表来做优化。5.3 哈夫曼树从带权路径长度到压缩编码哈夫曼树的目标是让带权路径长度WPL最小。所谓WPL就是把每个叶子节点的权值乘以从根到该叶子的路径长度再加总。构造方法很简单每次从集合里取出权值最小的两个节点合并出一个新的父节点父节点权值等于两个子节点权值之和放回集合重复直到只剩一棵树。我每次讲到这里都会提醒学生不要只会背步骤要理解“为什么每次取最小的两个”。因为路径长度越短的节点如果放上权值大的字符乘积就会变大反过来把权值大的字符放在离根更近的位置总消耗才会最小。每次取最小的两个合并本质是在动态规划全局最优这是一种贪心策略而且它的贪心是安全的数学上可以证明最终结果是全局最优。哈夫曼编码就是利用这棵树给字符分配二进制编码左分支0右分支1从根走到叶子就是编码。由于任意一个叶子编码都不是另一个叶子编码的前缀解码时不会产生歧义。ZIP、JPEG等压缩算法的底层思想都和哈夫曼编码有关。考试里算WPL时只要严格按照“每次取最小两个”的顺序画树结果就不会错。5.4 表达式树后序表达式怎么变成树表达式树是一种把运算对象放叶子、运算符放内部节点的树。前序遍历它得到前缀表达式中序遍历得到带括号的中缀表达式后序遍历得到后缀表达式。编译器在把源代码翻译成机器指令时经常会先构造语法树再通过遍历生成中间代码。比如表达式(3 4) * 2根节点是乘号左子树是加号、3和4右子树是叶子2。对这棵树做后序遍历得到3 4 2 *这就是后缀表达式。栈计算器寄托后缀表达式完成计算整个过程不需要管括号优先级。你会发现树的遍历不只是刷题用的在编译器、解释器里就是实实在在的核心操作。5.5 哈希树与Merkle Tree树也能做完整性校验热词里还出现了一个容易被忽略的“哈希树”它其实是一种应用型树结构。Merkle Tree就是典型的哈希树叶子节点保存数据块的哈希内部节点保存两个子节点哈希拼接后再取哈希的结果。因为父节点的值受所有后代影响只要任何一个数据块被改动一路向上传到根节点的哈希就会变化。它最出名的应用是在P2P网络和区块链里做数据完整性校验。不需要下载全部数据只要沿着某一条路径拿几个兄弟节点的哈希就能验证某个数据块是否被篡改。树在这里的最大贡献是把“验证整个集合”的代价压缩成了“验证一条路径”的代价。6. 设备树与时钟树当树走进硬件世界6.1 什么是设备树设备树是嵌入式Linux中描述硬件资源的一种机制它用节点和属性的方式把CPU型号、内存基址、外设地址、中断号、时钟频率等信息写成树交给内核在启动时读取。这样做的好处是内核源码不需要为每一块板卡写死大量平台代码换一块板子往往只需要换一棵设备树。实际开发中经常见到.dts、.dtsi和.dtb文件。.dts是设备树源文件.dtsi是公共的包含文件.dtb是编译后的二进制文件由内核在启动阶段解析。6.2 一个最小设备树片段设备树的基本单元是节点node每个节点下可以挂属性和子节点/dts-v1/; / { compatible demo,board-v1; cpus { cpu0 { compatible arm,cortex-a7; device_type cpu; }; }; memory80000000 { device_type memory; reg 0x80000000 0x20000000; }; uart0: serial10000000 { compatible demo,uart; reg 0x10000000 0x1000; interrupts 5; clock-frequency 24000000; }; };这里可以看到几个核心要素根节点代表整块板卡compatible属性告诉内核这块板卡属于哪一类平台cpus、memory、uart0是子节点分别描述CPU、内存和串口外设reg描述寄存器地址和范围interrupts描述中断号。最关键的设计是compatible。内核通过这个字符串去驱动的设备匹配列表里查找对应驱动所以设备树和驱动之间最重要的桥梁就是这段字符串。修改设备树时compatible一旦写错驱动根本不会被加载而且日志里经常只留下很模糊的提示排查起来非常痛苦。6.3 时钟树另一种“树”讲到设备树就绕不开时钟树。现代SoC内部有很多时钟源、锁相环和分频器它们之间天然是分层的晶振给主PLL提供基准时钟PLL锁定后输出高频时钟再经过一路路分频送给CPU、内存和外设。调试时经常要沿着时钟树追一条链路确认某个外设的时钟是否被正确打开频率是否配置到位。设备树里的clocks属性就是描述这种父子依赖关系的一种方式。虽然这里的“树”和算法教科书里的二叉树、B树不在同一个抽象层级但“父节点、子节点、祖先、后代、从根到叶子的路径”这些树的思维方式是完全一致的。你在学算法时培养的树形思维到了硬件调试里一样能用上。6.4 设备树和算法树的共同点有人可能会问一个偏软件算法一个偏硬件底层放在同一篇文章里会不会太跳其实两者的共同点非常直观。第一它们都用层级关系把复杂系统拆成小模块第二它们都强调“路径”这个抽象第三查找和匹配的效率都取决于树的高度和路径长度。学会用树的结构化思维去看待系统你会发现很多领域里的“树”都是可以互相印证的。7. 刷树题最容易踩的坑和我的实战习惯7.1 递归边界别只写“root为空”二叉树递归题的边界条件不只是root is None。比如计算高度时空树到底返回-1还是0会直接影响答案判断平衡二叉树时递归函数返回的不应该只是布尔值通常还要把子树高度一起带上来。我写代码之前会先想清楚一个问题这个递归函数到底返回什么返回值可以是int、bool甚至TreeNode一旦返回值的定义不清晰后面所有逻辑都会跟着乱。7.2 自顶向下和自下而上的区别树形题目有两种明显不同的思路。自顶向下是带着父节点传下来的信息比如路径和、深度、是否满足某个条件从根一直往下走每次进入子节点前先更新状态。自下而上则是递归拿到左右子树的返回值然后在父节点做汇总。求树的直径、最大路径和这类题目几乎都是自下而上因为路径往往要穿过某个节点必须先知道两侧子树的结果再回到父节点合并。用错方向是刷树题最常见的卡壳原因。我的判断方法是如果题目答案需要在子树结果基础上合并那就用自下而上如果答案只需要在路径上维护一个状态那就用自顶向下。7.3 复杂度分析别凭感觉树的递归复杂度不能靠猜。普通遍历每个节点访问一次整体O(n)。但如果递归函数内部在每一层都还要遍历整棵子树复杂度就可能到O(n log n)甚至O(n^2)。我常用的粗略估计方法是递归里如果只在当前节点做常数时间操作总复杂度就是O(n)如果每一层都要对子树做额外扫描那就需要像归并排序那样用主定理去估算。7.4 动手画树比看十道题都管用遇到不熟的树题我几乎都会先画一棵包含极端情况的树比如只有左孩子、只有右孩子、只有一个节点、空树。每次画完都能提前抓住不少边界情况。这个方法听起来土但确实非常有效尤其是递归写不下去的时候把树一画每一层应该返回什么、应该怎么处理空值往往一目了然。7.5 面试时如何组织树题答案面试和笔试不一样面试官更看重思路而不是直接把代码默出来。我推荐的现场答题顺序是先明确递归函数的定义包括入参和返回值说完边界条件再讲当前节点要做的事最后才写代码。这样即使代码里有瑕疵面试官也知道你思路清楚而不是凭记忆默写模板。如果你只想记一句话我的建议是遇到树先画出来再想递归函数返回什么。树的代码再花哨本质上都是在回答“这一步我要给父节点返回什么”。这也是我把这版笔记命名为V2的原因——第一版我背了很多结论第二版才开始真正理解每个结论是怎么推出来的。希望你不用绕我走过的这条弯路。