二叉树从实现到实战：建树、遍历、搜索与公共祖先全解析

上周帮A同学看课设代码，他交的“二叉树及其实现”作业，画图很漂亮，注释很整齐，一运行却只输出一个空白。我问他树是怎么建的，他说“就new了一个根节点，然后没有然后了”。这个场景挺典型的：概念都听过、结构图都能画，但真正要自己动手实现一棵二叉树，很多人就断在了“从图到代码”这一步。

这篇文章就围绕二叉树的完整实现展开。我会从存储结构选型说起，把建树、遍历、高度统计这些基础操作全部敲一遍，再把非递归遍历、搜索树、层序遍历、最近公共祖先这几个实战模板一并给出，最后聊聊我在实际写代码时踩过的坑。适合正在学数据结构的初学者，也适合准备笔试、面试前突击复习的开发者。你不是来看“什么是二叉树”的，你是来搞清楚“二叉树到底怎么用代码跑起来”的。

1. 从一次课程考核说起：看懂二叉树不等于会用二叉树

1.1 会画图、会写注释，代码却跑不出结果

A同学那版作业的问题，我拆开看其实就一句话：他把树的“逻辑形态”当成了“程序实现”。他定义好了节点类，也在主函数里创建了根节点，甚至画了完整的树形结构图。但除了根节点之外的所有节点，代码里压根没有创建，更没有把父子关系用指针或引用挂接起来。

这种问题在初学者里特别常见。二叉树的难点不在于节点的结构，而在于树是递归定义的：一棵树由根节点、左子树、右子树组成，子树本身又是一棵树。如果你想用代码表达一棵树，就必须让某个操作既能处理整棵树，也能递归地处理子树。这也是二叉树在数据结构课程里被称为“分水岭”的原因——它逼着你第一次真正理解递归，而不只是背递归公式。

1.2 二叉树的精确描述与四种基本形态

先把这个基础说清楚。二叉树是每个节点最多只有两个子节点的树结构，两个子节点分别叫左孩子和右孩子，左右的位置一旦定下来就不能互换。比如同样两个节点，一个是“根在左孩子上面”，一个是“根在左孩子左边”，画出来是两种不同的树，因为左右顺序不同。

较严格的教材会这样描述：一棵二叉树要么是空树，要么由一个根节点加上左子树和右子树构成，而左右子树仍然可以是二叉树。这里最容易被忽略的是第一种情况——空树。很多人一想到树就觉得必须有节点，但在递归实现里，空指针恰恰是递归的出口和退出的条件。我后面所有代码的递归边界都是if root is None，没有这一步，整个递归会无限往深处钻，最终栈溢出。

二叉树有四种基本形态：

• 空二叉树；
• 只有根节点；
• 只有左子树的二叉树；
• 根节点同时拥有左右子树的二叉树。

注意，只有右子树的情况，本质上也是第三种或第四种里的一种，因为“左子树为空、右子树非空”依然是一棵合法的二叉树。初学者容易把“最多两个子节点”理解成“必须两个子节点都非空”，这是后续写代码时很多空指针错误的来源。

1.3 为什么偏偏是二叉树：二分的价值

学了二叉树之后，很多同学会问：为什么不是三叉树、四叉树？我自己的理解是，二叉是“递归分解”里门槛最低、表达力又足够的形态。一个问题可以只分成左右两个子问题，由此带来的递归代码足够简单，却又涵盖大部分分治场景。

更关键的是，多叉树往往可以转换为二叉树。比如树的孩子兄弟表示法，把每个节点的第一个孩子作为左孩子，把下一个兄弟作为右孩子，就变成了一棵二叉树。堆、哈夫曼树、搜索树、表达式树这些底层结构，也都建立在二叉形态之上。所以在动手实现之前，先把“二叉树为什么值得做”想明白，后面学AVL树、红黑树、B树甚至线段树时，你会发现很多思维模型是共通的。

2. 动手前的关键选择：存储结构、语言与环境约定

2.1 链式存储与顺序存储，到底用哪种

写实现之前，先决定树的存储方式。这是很容易被忽略、但会影响后续所有代码的一步。

二叉树的存储常见有两种：

顺序存储的关键是下标关系：从0开始编号时，节点 i 的左孩子下标是2*i+1，右孩子是2*i+2，父节点是(i-1)/2取整。但普通二叉树中间可能出现大量空位，比如一棵只有右链的树，用顺序存储会像一个长度很大的数组，中间全是空值，浪费非常严重。链式存储就没有这个问题，每个节点按需创建，空子树直接用一个None表示。

我的建议是，绝大多数“实现二叉树”的场景都用链式存储。顺序存储真正的主场是堆这一类完全二叉树，没必要把所有二叉树都塞进数组。后面我会把链式存储和顺序存储结合起来用——用一层层补齐的方式描述树的形态，然后用链式结构真正构建出来，这样既直观又贴近实战。

2.2 节点定义与语言选型

接下来是节点。无论用什么语言，链式存储的核心都是同一个：数据域加左右引用。我用 Python 演示，因为代码足够短，专注表达逻辑本身，不纠结内存管理：

class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None

如果你习惯 C 语言视角，节点就是结构体加指针：

struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; };

语言的差异不影响树的逻辑。Python 里self.left = None就相当于 C 里的空指针；访问node.left相当于通过引用跳转到子节点。创建一棵只有根节点结果的树只需要：

root = TreeNode(1)

真正关键的是，要把None当成一个合法节点来看待。它不是“出错”，它代表的是“这里没有子树”。理解这一点，递归的边界条件才有意义。

2.3 一个必须提前说清的约定：序列与树的对应关系

我在整理这篇文章的代码时发现，很多人对“用数组描述二叉树”有误解。比如数组[3, 9, 20, None, None, 15, 7]，它到底对应哪棵树？这里有一个默认约定：按层序从上到下、从左到右填进数组，None表示该位置没有节点。

但这里有个容易被忽视的细节：同一个序列，只有在遍历方式也确定时，才能唯一对应一棵树。比如先序序列“A B C”，如果不说明空节点用#表示、也不规定哪些位置是空子树，它能画出至少三种不同的树。所以当人家给你一个序列让你建树时，第一反应应该是问清楚：这个序列是层序、先序还是中序？空位用什么标记？没搞清楚这两点，后面所有代码都可能对着错误的树在调。

3. 核心实现一：从层序序列构建二叉树并完成基础操作

3.1 建树：先铺所有节点，再逐层挂接

现在进入正题。假设输入是一个层序序列，比如[3, 9, 20, None, None, 15, 7]，对应的树是根节点3，左孩子9，右孩子20，20的左孩子15，右孩子7，9的左右孩子都是空。我想把它构建成一棵链式存储的二叉树。

一种相当稳妥的思路是：先把数组里所有非空值都创建成独立的节点对象，放在一个数组里；然后再遍历一次数组，按下标关系把左右孩子挂上去。代码如下：

def build_from_level_order(values): if not values: return None nodes = [None if v is None else TreeNode(v) for v in values] for i in range(len(values)): if nodes[i] is None: continue left_idx = 2 * i + 1 right_idx = 2 * i + 2 if left_idx < len(values): nodes[i].left = nodes[left_idx] if right_idx < len(values): nodes[i].right = nodes[right_idx] return nodes[0]

这个写法为什么稳？因为nodes列表里放的是对象的引用，当nodes[0].left = nodes[1]执行时，不只是把下标连过去，而是把节点9整个对象挂到根节点的左引用上。二次遍历时即使后面的节点还没有挂好孩子，也不影响已建立的关系。

我建议初学者先不要尝试“一边读取一边建树”的队列写法，那个对空节点的判断容易出错。先把“建节点”和“挂节点”两个阶段分开，逻辑上不容易漏掉边界，这是对初学者最友好的拆解方式。

3.2 三种递归遍历：先序、中序、后序

建好树之后，最经典的操作就是遍历。递归遍历的实现出奇地简洁，因为树的递归定义直接给了你递归结构：

def preorder(root): if root is None: return print(root.val, end=' ') preorder(root.left) preorder(root.right) def inorder(root): if root is None: return inorder(root.left) print(root.val, end=' ') inorder(root.right) def postorder(root): if root is None: return postorder(root.left) postorder(root.right) print(root.val, end=' ')

三者的差别只有一个：访问根节点的位置在什么时候。先序在左子树之前、中序在左子树之后右子树之前、后序在左右子树都完成之后。你可以把树的访问想象成一次“巡视”：先序是到了每个节点先打卡再去巡视下属；后序是把下属都巡视完了才回来打卡。三种顺序只是打卡时机不同。

以上面的树为例，运行结果分别是：

有两点提醒。一是递归函数里的return写在第一行，不要省略这个if root is None的判断。你会发现访问节点的语句在None判断之后，这就保证了“空树下一次递归调用不会崩”。二是别试图在脑子里完整展开一棵大树的递归过程，那是给编译器看的。你只需要信任递归：左子树调用会完整处理左子树，右子树调用会完整处理右子树，这个信任建立起来，遍历代码就没什么玄学了。

3.3 高度、节点数、叶子数：递归三件套

看完遍历，我们再写几个最常见的树属性计算。这些操作的模板完全一致：先处理空节点返回一个默认值，再分别对左子树和右子树调用同样函数，最后把结果组合起来。

树的高度是自底向上返回的，空树高度为0，单节点树高度为1：

def tree_height(root): if root is None: return 0 return 1 + max(tree_height(root.left), tree_height(root.right))

节点总数递归累加即可：

def count_nodes(root): if root is None: return 0 return 1 + count_nodes(root.left) + count_nodes(root.right)

叶子节点是左右孩子都为空的节点，所以判断逻辑是：空树返回0；如果一个节点没有左孩子也没有右孩子，返回1；否则返回左子树的叶子数加右子树的叶子数：

def count_leaves(root): if root is None: return 0 if root.left is None and root.right is None: return 1 return count_leaves(root.left) + count_leaves(root.right)

这三个函数放在一起看，你会发现规律：递归问题天然地分成了空节点、叶子节点、内部节点三类情况。空节点返回基础值，叶子节点返回本层结果，内部节点把左右子树的递归结果合并。这个“递归三件事”思维，是二叉树实现中最重要的心法，后面做题时很多题目都可以套这个框架。

4. 核心实现二：自己维护栈，把递归遍历改写成非递归

4.1 为什么非递归遍历是绕不开的技能

很多人觉得递归遍历已经够用，为什么要折腾非递归？三个现实理由驱动我把它看懂：

第一，系统给函数调用的栈空间是有限的。树如果退化成一条链表，递归深度会等于节点数，几千层的递归很容易把调用栈打爆。第二，很多笔试环境里，面试官会要求“不用递归实现遍历”，考查你到底理解的是递归公式还是函数调用本质。第三，非递归版本其实就是把系统递归时隐式发生的事，用显式数据结构重做一遍，这个“显式化”过程能极大加深你对栈的理解。

4.2 先序非递归：栈的后进先出完美匹配

先序遍历的顺序是“根、左、右”。用栈模拟时，为了让左子树先被处理，入栈顺序应该反过来：根先入栈，出栈访问后先压右孩子，再压左孩子。因为栈后进先出，后压的左孩子会先弹出。

def preorder_iter(root): if root is None: return stack = [root] while stack: cur = stack.pop() print(cur.val, end=' ') if cur.right: stack.append(cur.right) if cur.left: stack.append(cur.left)

这段代码背后的逻辑是：每次从栈里取一个“待访问子树”的根，打印之后，把它的左右子树压栈继续处理。只要栈不为空，就说明还有子树没有访问完。

4.3 中序非递归：一路向左到底，再反弹

中序序列是“左、根、右”，而这个顺序用单纯左右交换入栈是做不到的，因为要先走到整棵子树最左侧，才能打印最左边的叶子。所以中序非递归需要两步走：先不断把左孩子压栈，直到没有左孩子；然后弹出节点访问，再转向右子树继续同样的过程。

def inorder_iter(root): stack = [] cur = root while stack or cur: while cur: stack.append(cur) cur = cur.left cur = stack.pop() print(cur.val, end=' ') cur = cur.right

我第一次写这个函数时，一直想不通为什么最后一步是cur = cur.right，而不是直接继续弹栈。后来想明白了：当前节点既然已经弹出并访问，它的左子树已经全部处理完，下一步只需要处理它的右子树。如果右子树为空，cur会变成None，外层循环再次进入时就会继续弹栈，处理父节点。这个“左到底、弹栈、转右”的模型，就是中序非递归的核心。

4.4 后序非递归：利用先序变体，避免麻烦的标记法

后序是“左、右、根”，这是三种遍历里非递归最难写的。我见过不少用“记录上一个访问的节点”来判断该不该弹出的版本，细节容易出错。一个更简洁的方案是：把后序看作“根右左”的逆向。

先按“根、右、左”的顺序做一次变体遍历，再把结果反转，就得到了“左、右、根”。而“根、右、左”和前序“根、左、右”只有压栈时先压左还是先压右的区别：

def postorder_iter(root): if root is None: return [] stack = [root] result = [] while stack: cur = stack.pop() result.append(cur.val) if cur.left: stack.append(cur.left) if cur.right: stack.append(cur.right) return result[::-1]

这段代码先做的是“根、右、左”，但我压栈时先压左再压右，弹出顺序就是先右后左，于是result里存的是“根右左”，最后[::-1]反转成真正的“左右根”。这是我个人最推荐给初学者的后序非递归写法，因为它建立在已经掌握的前序逻辑之上，不需要引入额外的访问状态标记。

5. 实战中的高频模式：搜索树、层序遍历与最近公共祖先

学完基础操作，二叉树的价值主要体现在具体应用模式上。这一节给三个我在实际工作中反复用到的模板，也帮你把基础实现和真实题目连起来。

5.1 二叉搜索树：左小右大的有序世界

二叉搜索树每个节点满足：左子树所有节点值小于当前节点，右子树所有节点值大于当前节点。这个有序性让查找变成沿路径的一次线性行进：

def search_bst(root, key): while root and root.val != key: if key < root.val: root = root.left else: root = root.right return root

每一轮比较都排除掉一棵子树，平均复杂度是O(log n)。这个结构其实就是“二分查找思想的动态版本”。但你必须知道它的局限性：如果插入顺序是1、2、3、4、5，树会退化成一条只有右子树的链，查找退化成O(n)。这也是为什么后来有AVL树、红黑树这些自动平衡的结构出现。学完二叉树实现以后往这个方向走，路是顺的。

5.2 层序遍历：队列天然匹配“一层一层看”

层序遍历和前三种遍历不同，它不依赖递归深度，而是逐层处理。实现上用队列，每一轮先把当前层所有节点取出，再把下一层节点放入。这样既可以“按层输出”，也方便做每层统计。

from collections import deque def level_order(root): if root is None: return [] q = deque([root]) result = [] while q: level_size = len(q) level_vals = [] for _ in range(level_size): cur = q.popleft() level_vals.append(cur.val) if cur.left: q.append(cur.left) if cur.right: q.append(cur.right) result.append(level_vals) return result

这段代码的关键点是先记录level_size = len(q)，因为它必须保证当前层节点全部处理完才会进入下一层。如果不用这个变量，队列里会混着上一层和下一层的节点，层次就分不清了。层序遍历也是二叉树和“广度优先搜索”之间的桥梁，很多树的宽度类问题都能在这个模板上改动解决。

5.3 最近公共祖先：信任递归的返回值

最后看一个非常经典的递归应用：给定两个节点p和q，找它们的最近公共祖先。这个问题让我印象很深，因为代码极短，却需要你完全信任递归返回值：

def lowest_common_ancestor(root, p, q): if root is None or root.val == p or root.val == q: return root left = lowest_common_ancestor(root.left, p, q) right = lowest_common_ancestor(root.right, p, q) if left and right: return root return left if left else right

逻辑是这样的：在某个节点上，我去左子树找p或q，去右子树找p或q。如果两边都找到了，说明p和q分别位于该节点的左右子树中，当前节点就是最近公共祖先。如果只有一边找到，说明两个节点都在同一侧，答案应该由那一侧的递归结果决定。这个过程没有显式的路径记录，靠的是递归自底向上返回结果，理解它比背下它更重要。每次看到这个函数，我都会想起前面说的“递归三件事”——边界条件、本层逻辑、左右子树的递归调用，它正是这个框架的极致体现。

6. 踩过的坑与最后想交代的几句话

6.1 空指针不是异常，而是递归的出口

我在调整A同学代码时，发现他写递归遍历之前总是判断root.left is not None，然后再进入左子树。这种写法看似小心，其实绕了远路。更干净的方式是直接调用func(root.left)，让函数进入第一行就判断root is None并返回。

这个思维习惯上的差异，根源在于“把空子树当成了不合法状态”。实际上空子树就是树的一部分，不是出错了。把空指针视为合法状态并统一处理，代码的边界会简洁很多。而颠倒的写法往往还会漏掉某些空节点，导致程序崩得莫名其妙。

6.2 同一个序列，没有约定就无法唯一建树

A同学后来又给我看了一段代码，他想用先序序列“A B C”建树，但没约定空节点标记，结果建出来的树完全不是他想要的那个。先序序列本身并不足以唯一恢复一棵二叉树，除非同时给出空节点标记，比如“A B # # C # #”这样，用#表示空子树。

这里我想强调一个容易被坑的细节：即使数组里有#标记，同样一个序列也往往只在某一特定遍历顺序下有意义。层序序列、先序序列、中序序列给出的信息量和建树方式都不同。别人给你一个序列后，先确认“这是什么顺序、空位怎么标记”，再动手构建，能省去很多调试时间。

6.3 树形退化和递归深度是两件必须提前想的事

当树退化成链表时，递归遍历的深度等于节点数。Python 默认递归深度上限大约在1000层左右，节点稍微多一点，递归就报错。应对方法有两个方向：一是给二叉搜索树这类结构做自平衡处理，防止树退化；二是在可能很深的情况下改用非递归遍历。

我在实际写解析器、表达式求值这类工具时，经常遇到深度很大的树，所以非递归遍历并不是面试噱头，而是工程上真实需要的手段。如果你只是学习阶段，我建议把第4节的三个非递归写法亲手敲一遍，不求一次写对，关键是理解每一步维护栈的意义。

6.4 我个人练二叉树实现的一点习惯

最后分享一个对我自己帮助很大的方法：找一棵只有6到7个节点的树，画出它的结构，然后手工模拟一遍“递归函数调用顺序”。我指的是真的拿纸笔写写左侧的调用栈变化，而不是盯着屏幕发呆。这个过程会暴露出很多你以为懂、其实没懂的地方，比如中序非递归里cur的转移时机，比如后序变体里压栈顺序如何影响结果。

还有一个小技巧，调试时可以用带缩进的输出把树打出来，快速确认结构对不对：

def print_tree(root, depth=0): if root is None: return print(" " * depth + str(root.val)) print_tree(root.left, depth + 1) print_tree(root.right, depth + 1)

这种输出方式比脑补树的形状直观太多。我每次建完树都会先打印一遍，确认左右子树关系符合预期，再继续后续操作。二叉树的学习就是这样，概念听一百遍，不如一次完整的实现来得深刻。你现在手边如果有编辑器，拿上面的代码跑一遍，跑出来的结果，就是你对这棵树真正的理解。