二叉树入门到进阶：遍历、重建、深度与搜索二叉树全攻略

树这个东西很多写代码的朋友一开始其实是有点抗拒的。数组、链表再难好歹是线性的顺着一个方向就能摸到头。可树不一样分叉了递归了一下子脑子就转不过弯。但我跟你说句实话二叉树真的没有想象中那么玄乎你在电脑上整理文件夹、看一场淘汰赛的对阵表、翻公司组织架构图其实都在用树形结构。甚至编译器解析你写的表达式、搜索引擎建索引、数据库维护索引底层都有二叉树或者它的变体在撑着。可以说学数据结构不碰二叉树就像学做饭不会炒鸡蛋后面啥都接不上。这篇我想用大白话把二叉树从概念到实操完整过一遍它到底是什么、在代码里怎么存、四种遍历怎么玩、给了先序和中序怎么把树还原出来、深度怎么算、搜索二叉树是怎么回事最后再聊聊线索二叉树这个容易被忽视但考得不少的知识点。内容尽量照顾到零基础的人也适合准备面试想快速过一遍的朋友。1. 先弄明白二叉树到底是个什么结构1.1 为什么有了数组和链表还需要树你可能会想数组、链表不都能存数据吗为什么要搞出个树来问题在于它们都是线性结构表达不了“层级关系”。你要存一个公司的部门架构总经理下面有技术部、市场部、行政部技术部下面还有前端组、后端组、测试组用数组怎么存硬存也能存但“谁是谁的下级”这层关系就丢了。你要找某个人的所有下属得遍历整个数组去匹配父子关系效率很低。树就是专门为解决这类问题设计的每个节点往下挂若干子节点天然就能表达层级、嵌套、归属这类关系。而二叉树是树里最简单、最规整、也最适合入门的一种——每个节点最多只有两个分支。1.2 树的那些术语其实用家族关系就能说清我第一次学树的时候被一堆术语砸得头晕现在回头看只要把树想象成一个家族族谱各术语都能对号入座根节点一棵树最顶上的那个节点整个家族的“老祖宗”。一棵树有且只有一个根。父节点和子节点A直接连着BA就是B的父节点B就是A的子节点。就像你爸是你的父节点你是你爸的子节点。兄弟节点同一个父节点下面的几个子节点彼此就是兄弟。叶子节点没有再往下挂子节点的节点相当于家族里“没有后代”的那一辈。节点的度一个节点拥有的子树个数。注意树的“度”和“出度”有点混用考试里记住二叉树每个节点的度最大是2就行。深度和高度这是最容易绕晕的一组。我习惯用“从根往下数”和“从叶子往上数”来区分深度描述的是从根到某个节点的边的条数高度描述的是从某个节点到最远叶子节点的边的条数。说白了一个往下量一个往上量。后面第5节我还会详细展开。1.3 满二叉树和完全二叉树别搞混这两个概念是后面堆排序、优先队列的基础也是面试爱问的。满二叉树每一层的节点数都堆满了。第1层1个第2层2个第3层4个这样下去。深度为k的满二叉树总节点数是2^k - 1个。完全二叉树它的定义更微妙——除了最后一层以外上面每一层都是满的而且最后一层的节点必须从左往右连续排列不能空着右边去填左边。我给你画个对照感受一下满二叉树 完全二叉树 不是完全二叉树 1 1 1 / \ / \ / \ 2 3 2 3 2 3 / \ / \ / \ / / \ \ 4 5 6 7 4 5 6 4 5 7左边那个是满的不用解释。中间那个第三层有4、5、6从左往右数7还没排上但没出现“左边空着右边有节点”的情况所以算完全二叉树。右边那个第三层4、5挂了两个7却单独挂在3的右边6的位置空着这就破坏了“从左到右连续”的规则不是完全二叉树。为什么完全二叉树这么重要因为它和数组存储完美匹配——所有节点在数组里是连续存放的不浪费空间而且父子节点的下标能用公式直接算出来。这个在下一节会讲到。2. 代码里的二叉树存储方式怎么选2.1 顺序存储用数组也能存树二叉树可以用数组存思路是把树上的节点按“从上到下、从左到右”的顺序填进数组根节点放下标0然后依次往后排。关键是下标之间有数学关系。假设某个节点的下标是i从0开始那么它的左孩子下标是 2i 1它的右孩子下标是 2i 2它的父节点下标是 (i - 1) / 2 向下取整用C语言或者Python里的数组就能轻松实现。这个方案对完全二叉树特别友好数组里每个位置都有意义不会浪费。但问题也很明显如果树不是完全二叉树比如一棵只有右子树的“斜树”用数组存就会空出大量位置。深度10的斜树总共就十几个节点用数组存却需要2^10-1个位置绝大多数白白空着。所以顺序存储通常只在完全二叉树场景下使用经典的堆排序就是这种玩法。2.2 链式存储最主流的二叉树表示实际写算法题、做业务开发绝大多数人用的是链式存储。每个节点就是一个对象里面保存数据再放两个指针引用分别指向左孩子和右孩子。C语言里可以这样定义typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode;Python里用类表示更直观class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right你可能会发现这个结构和双向链表有点像——链表是前驱、后继两个指针二叉树是左孩子、右孩子两个指针。只不过链表是“一维”的二叉树是“二维”的指针指向的是下一层而不是前后。那什么时候用链式、什么时候用数组我的习惯是普通二叉树、结构不固定的树一律链式而堆、线段树这种底层总是完全二叉树的场景直接上数组省内存且计算下标方便。面试时大多数题目默认给你链式节点结构你得两种都能随时切换。2.3 创建一棵二叉树的实操写法光定义节点类还不够得会手动建树。比如要建这么一棵树1 / \ 2 3 / \ 4 5用Python构建def build_example_tree(): root TreeNode(1) root.left TreeNode(2) root.right TreeNode(3) root.left.left TreeNode(4) root.left.right TreeNode(5) return root这种方式简单直接适合写题时搭测试用例。如果需要从数组批量建树通常用层序方式把数组按完全二叉树的规则一个个插入节点遇到空节点跳过。这里就不展开先知道有这回事即可。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]这种写法的好处是跟定义一一对应坏处是每层递归都创建新列表效率一般。面试时这样写没问题但生产环境或者刷性能要求高的题通常改成辅助函数传结果列表def preorder(root, res): if not root: return res.append(root.val) preorder(root.left, res) preorder(root.right, res)三种遍历分别有什么用这里说几个典型场景先序拷贝一棵树时非常自然先复制根再复制左右子树也是树序列化的常用顺序之一。中序在二叉搜索树里中序遍历得到的结果是有序的。这是很多BST相关题目的突破口。后序先处理完左右子树再处理根适合做“树的销毁”“计算整棵树大小”这类自底向上的操作。删除节点时也必须用后序先删孩子再删自己否则把父节点删了孩子就找不到了。3.2 层序遍历广度优先的树上版本层序遍历就是逐层从左到右访问节点从根开始一层层往下扫。实现时需要一个队列from collections import deque def level_order(root): if not root: return [] result [] q deque([root]) while q: level [] for _ in range(len(q)): node q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) result.append(level) return result代码里的len(q)是精髓。在进入每一层之前队列里正好存着这一层的所有节点循环range(len(q))次就能把这一层清空同时把下一层节点加进来。这样就完成了按层分组。层序遍历的经典应用是求树的最大宽度、判断一棵树是否是完全二叉树按层遍历时一旦出现空节点后面就不该再出现非空节点、打印树的“俯视图”等等。3.3 遍历背后的直觉递归就是在“自己用自己”我教别人的时候发现很多初学的人递归写不出来卡点是“想递归的时候脑子里非要模拟完整执行过程”。这其实没必要。以先序遍历为例你只需要相信preorder函数已经能正确遍历一棵树。那么你要遍历当前树就三步先输出根再用这个函数遍历左子树再用这个函数遍历右子树。至于是怎么遍历完的递归内部会处理。这种“相信函数已经实现功能”的心态是写递归最重要的思维方式不只是树链表、图都通用。4. 只给先序中序如何还原一棵树这个题目在笔试和面试里出现的频率极高已知一棵二叉树的先序遍历序列和中序遍历序列要求重建这棵树。4.1 为什么两种遍历就能唯一确定一棵树我先说结论先序中序 或 后序中序 都能唯一确定一棵二叉树但先序后序不行。原因在于先序序列的第一个节点一定是根。在中序序列里根节点把序列劈成两半左边是左子树的中序序列右边是右子树的中序序列。知道了左子树和右子树分别有多少个节点再回到先序序列里就能把左子树和右子树的先序序列也切出来。这样一路递归下去整棵树就重建出来了。而先序后序为什么不行因为先序确定根之后你只知道第一个节点是根但根后面是左子树还是右子树的开头无法确认。再看后序也只能确认倒数第一个是根根的左子树右子树边界依然无法确定。因此当树的某个节点只有一个孩子时先序后序会对应多种合法结构。4.2 手工推演亲手拆一次就知道原理来我带你走一遍完整推演。假设先序序列ABCDEFG 中序序列CBDAFEG第一步先序第一个是A所以根是A。第二步在中序里找AA左边是CBD右边是FEG。因此左子树的中序序列是 CBD右子树的中序序列是 FEG第三步左右子树各3个节点那么把先序序列 A 后面的BCDEFG分成两段前3个BCD是左子树的先序后3个EFG是右子树的先序。现在问题缩小为两个子问题左子树先序 BCD中序 CBD右子树先序 EFG中序 FEG先看左子树先序第一个是B中序CBD中B在中间左边是C右边是D。所以B的左孩子是C右孩子是D。再看右子树先序EFG第一个是E中序FEG中E在中间左边是F右边是G。所以E的左孩子是F右孩子是G。整棵树就出来了A / \ B E / \ / \ C D F G整个过程就是不断重复“先序定根、中序分左右”每次把问题拆成一半规模的两个子问题递归处理。4.3 递归代码实现用Python实现如下def build_tree(preorder, inorder): if not preorder or not inorder: return None root_val preorder[0] root TreeNode(root_val) root_index_in_inorder inorder.index(root_val) left_inorder inorder[:root_index_in_inorder] right_inorder inorder[root_index_in_inorder 1:] left_size len(left_inorder) left_preorder preorder[1:1 left_size] right_preorder preorder[1 left_size:] root.left build_tree(left_preorder, left_inorder) root.right build_tree(right_preorder, right_inorder) return root这里inorder.index(root_val)每次都要线性查找所以整体时间复杂度是 O(n²)。优化方案是在递归前先遍历一次中序序列把“节点值→下标”存成哈希表查询降到 O(1)整体复杂度就变成 O(n)。写题时如果树的规模大建议用哈希表优化如果只是搞清楚思路上面的简单版本够了。值得一提的是很多初学者会问如果节点值有重复怎么办这种情况确实有可能产生二义性。更稳妥的方案是用两个下标指针维护当前子树的边界而不是用切片构造新数组同时在哈希表里存下标列表来处理重复值。不过这是进阶话题新手先把基本版本跑通再考虑优化。5. 从根到叶的距离二叉树的深度“二叉树的深度”能上热搜说明太多人在这上面栽过跟头。它不只是算一个数牵涉到递归思想、边界条件、迭代实现等一系列问题。5.1 深度和高度先说清深度和高度在很多教材里定义略有差异但记住下面这组就够用根节点的深度是0或1取决于题目约定。LeetCode一般按根节点深度为1处理不少数法也有从0开始的你做题前先确认好否则边界条件容易错。节点的深度等于从根到该节点经过的节点数或边数。树的高度等于根节点的高度也就是从根到最远叶子的距离。面试时如果问“二叉树的最大深度”通常指从根到最远叶子节点的最长路径上的节点数。如果根为空深度就是0。5.2 递归求深度最优雅的解法要求树的最大深度用递归思考会非常顺畅。一棵树的深度等于左子树的深度和右子树的深度取较大值再加1这个1就是当前层根节点占的高度。def max_depth(root): if not root: return 0 left_depth max_depth(root.left) right_depth max_depth(root.right) return max(left_depth, right_depth) 1这段代码是不是短到让你怀疑但它就是这个问题的标准答案。递归过程可以这样理解一路向下走走到空节点返回0每往上一层就带着“下面已经算好的深度”加上1到了根节点得到的就是整棵树的最大深度。这个递归的时间复杂度是 O(n)每个节点访问一次空间复杂度是 O(h)h为树的高度最坏情况退化成链表会达到O(n)。5.3 迭代求深度层序遍历的另一个用处不用递归也能求深度而且思路更直观树有几层深度就是几。所以层序遍历一次用计数器记录层数即可def max_depth_iterative(root): if not root: return 0 from collections import deque q deque([root]) depth 0 while q: depth 1 for _ in range(len(q)): node q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) return depth这个版本和前面层序遍历的代码可以说是一模一样只不过把记录层数据改为记depth。这说明一个问题很多算法不是孤立的新知识而是同一类思想的变体。你层序写熟了求深度、求宽度、判断完全二叉树都是顺手的事。树深度的概念还会延伸到判断平衡二叉树——一棵树是不是平衡的要看左右子树高度差是否超过1。很多初学者直接对整棵树求深度再比较单独看一个节点没问题但要在所有节点上都满足于是递归里既要返回高度又要判断是否平衡这又是另一个经典题了先把深度本身吃透再上路。6. 搜索二叉树让查找快起来的树搜索二叉树Binary Search Tree简称BST是所有树形结构里最实用的一种。它红得发紫的原因只有一个查找、插入、删除的平均时间复杂度都能到 O(log n)比链表查找的 O(n) 快了一个量级。6.1 BST的核心性质左小右大说白了BST对所有节点都有同一个约束左子树上所有节点的值 根节点的值右子树上所有节点的值 根节点的值左右子树本身也必须分别是BST注意是“左子树上所有节点”不只是左孩子。这个条件保证了整棵树的全局有序性。例如下面这棵就是BST8 / \ 3 10 / \ \ 1 6 14中序遍历这棵树得到1, 3, 6, 8, 10, 14正好是一个递增序列。这是BST最重要的性质之一很多题目都靠它破题比如“判断一棵树是不是BST”“BST中找第k小的节点”。6.2 查找和插入两种写法都得上手查找的思路很简单从根出发目标值和当前节点比大小相等就找到目标值小就往左走大就往右走走到空节点就是不存在。递归版def search_bst(root, val): if not root or root.val val: return root if val root.val: return search_bst(root.left, val) return search_bst(root.right, val)迭代版def search_bst_iterative(root, val): cur root while cur and cur.val ! val: if val cur.val: cur cur.left else: cur cur.right return cur迭代版不依赖函数调用栈省内存而且流程清晰建议两种都练习。插入也类似找到合适的空位置挂上新节点就行def insert_into_bst(root, val): if not root: return TreeNode(val) if val root.val: root.left insert_into_bst(root.left, val) elif val root.val: root.right insert_into_bst(root.right, val) return root很多教材说BST不允许重复值遇到相等就直接忽略。但实际工程里经常需要处理重复常见方案是每个节点多维护一个计数器或者允许往右子树插入重复值。你自己设计时根据需求定面试默认无重复即可。6.3 BST的隐患会退化别天真BST的平均效率是O(log n)但这是建立在树“长得比较均匀”的前提下。如果你按有序序列1, 2, 3, 4, 5...依次插入树会变成一根右斜的链表1 \ 2 \ 3 \ 4这时候查找5要一路走到底复杂度变成O(n)跟链表没区别。这就是为什么会有AVL树、红黑树这些平衡二叉搜索树出现的意义——它们通过旋转操作保证树的高度始终在O(log n)范围。所以学BST不能只学操作还要有“树会退化”的意识。这也是面试官最爱的追问点之一你实现了BST那它最坏情况复杂度是多少如何优化能答出平衡树的概念就已经超出大部分人了。7. 线索二叉树让空指针也有价值线索二叉树是很多教材里“学了但感觉没学”的内容但既然热搜词里高频出现说明考试和面试真会问这里给你捋清楚。7.1 问题起源链表树里空指针太多了如果一棵二叉树有n个节点每个节点有两个指针域总共有2n个指针。其中指向孩子的有效指针只有n-1条不算根节点其他每个节点都有一个父指针指向它那么空指针数量就是2n - (n - 1) n 1比如有100个节点就有101个空指针。这些空间白白浪费了。线索二叉树的想法就是利用这些空指针指向遍历序列中的前驱或后继节点让遍历不用递归、不用栈也能进行。7.2 线索化的核心思想二叉树有四种遍历就有四种对应的线索树。教材里最常讲的是中序线索二叉树因为中序遍历是递归的线索化之后用循环就能遍历效率很高。线索化的规则是如果某节点的 left 为空就让它指向中序遍历中的前驱节点如果某节点的 right 为空就让它指向中序遍历中的后继节点但问题来了一个节点有空指针但你怎么区分这个指针本来指向孩子还是被改成指向前驱/后继了所以每个节点还要加两个标记位比如 LTag 和 RTagLTag 0 表示 left 是指向左孩子的LTag 1 表示 left 是指向前驱的线索。RTag 0 表示 right 是指向右孩子的RTag 1 表示 right 是指向后继的线索。拿最经典的例子一棵只有三个节点的树B / \ A C它的中序遍历是A - B - C。线索化后A的left为空没有前驱指向NULLA的right为空指向后继B。B是根left指向Aright指向C都有实子节点不需要线索。C的left为空指向后继前驱BC的right为空继承后驱NULL。这样当中序遍历走到A时A的right指向B但B的right已经指向C所以可以顺着线索一路走下去不需要递归回溯。线索化本身也对树做一次中序遍历区别是在访问节点时额外判断并设置线索。伪代码大概长这样def in_threading(node): if not node: return in_threading(node.left) # 处理当前节点的线索 if not node.left: node.ltag 1 node.left pre if pre and not pre.right: pre.rtag 1 pre.right node pre node in_threading(node.right)这里pre是中序遍历中刚访问过的那个节点也就是当前节点的前驱。每次访问完当前节点把它记下来等下一次访问下一个节点时就能反向补上前一个节点的后继线索。7.3 线索树的优劣和实际选择线索二叉树的优点很明显中序遍历不需要递归不需要显式的栈效率高而且可以用循环轻松找到任意节点的前驱和后继这在需要频繁做“找上一个/下一个节点”的操作时很方便。但它也有代价线索化本身需要一次遍历在线索化和普通操作之间切换有额外开销。插入、删除节点时不仅要改左右孩子指针还要维护线索的正确性比普通树的调整复杂得多。节点多了两个标记位存储上并没有真的省下多少内存。所以实际工程中它的存在感并不高。真正的高频使用场景反而是某些数据库索引结构、特定场景下的高效遍历需求以及——考试和面试。作为学习者理解它“为什么存在、怎么工作、有什么优缺点”就够了没必要自己去实现一个完整的线索树模块。我在实际学习过程中有一个体会二叉树这章的内容其实是一环扣一环的。存储方式决定操作复杂度遍历是所有操作的基础先序中序重建树本质上练的是递归切分BST把二叉树变成了实用工具线索树又展示了利用空指针的巧妙思路。遇到不会的题不要急着看答案先在纸上画一棵小树用最笨的办法走一遍往往就能找到规律——这个方法我带过不少人验证过比直接刷十道题都管用。