手把手教 | 树算法刷题路线终极版

▌ 技术引导
树算法刷题路线终极版，必须从数据结构底层开始构建，否则容易在中后期遇到性能瓶颈。我见过很多同学在LeetCode上刷题，一开始用递归写树的遍历，题越做越大，递归深度一超过系统限制就直接炸了，这根本不是算法问题，是工程实现细节的疏忽。树结构的遍历、构造、平衡、序列化、反序列化，这些基本技能必须打牢，否则后续各种变体题都看不懂。别试图用高级语言的框架类库来糊弄，哪怕你用Python的collections模块，也要理解它背后是如何实现的。我踩过坑，用DFS写树的深度优先遍历，结果因为没处理节点的父子关系，导致结果混乱。真实经验是，刷题前务必掌握如何手动实现树的插入、删除、查找，再结合框架的高级API。记住，每一道树算法题，本质上都是在测试你对递归、状态转移、边界条件的掌控力。

▌ 技术参考

一 基础数据结构必须自己实现
树结构的节点定义是刷题的第一步，我见过太多人直接用框架的TreeNode类，结果在处理子节点时逻辑混乱。正确的做法是自己用class实现节点，包含val、left、right三个属性，并手动添加构造函数。比如在Python中，可以用class Tree: def __init__(self, val=0, left=None, right=None): self.val = val; self.left = left; self.right = right。这样做的好处是能清楚知道每个节点的引用关系。如果用C++或Java，建议用struct或class来封装节点，并在构造时传入左右子节点。刷题初期千万不要依赖第三方库的TreeNode类，否则你永远无法真正理解树的结构。我遇到过用递归构造树，结果因为没处理null节点，导致整个树的结构被破坏，最后调试了整整三个小时。

二 树的遍历必须掌握三种方式
树的遍历是刷题的核心，必须掌握前序、中序、后序三种遍历方式。我见过很多同学在刷题时只写前序，中序和后序遇到就懵。正确的做法是用递归和迭代两种方式分别实现三种遍历，特别是迭代方式，必须理解栈的使用方式。比如在Python中写前序遍历，可以用递归方式：def preorder(root): if not root: return; print(root.val); preorder(root.left); preorder(root.right)。迭代方式则是用栈，先压入根节点，然后循环弹出并压入右、左节点。中序和后序的处理顺序不同，必须注意左中右或右中左的顺序。尤其在处理二叉搜索树时，中序遍历的结果是有序的，这是关键点。如果只掌握一种方式，后续题目如序列化、反序列化、层序遍历都可能无法正确实现。

三 树的构造与转换必须灵活
树的构造方式多种多样，比如从数组构造二叉树、从字符串构造表达式树等。我见过很多同学在构造树过程中不注意左右子树的位置，导致整棵树结构错误。例如，在LeetCode中常见的从数组构造二叉树的题，需要用索引计算左右子节点，比如左子节点为2i+1，右为2i+2，且确保i不会越界。如果数组中存在null节点，必须用特殊符号表示，比如#，并用队列或栈来处理。在反序列化过程中，必须解析字符串并逐层构建树结构，比如用split()方法分割字符串，然后逐个节点处理。构造和反序列化是树算法的高频操作，必须熟练掌握，否则无法应对复杂题目。

四 递归与迭代的抉择必须有边界
递归和迭代的实现方式各有利弊，必须根据题目特点选择。我见过很多题目用递归写更简洁，但遇到深度过大的情况，就会栈溢出。例如，在LeetCode 104题中，递归实现的简单性让人上头，但超过1000层就会报错。这时候必须用迭代方式，比如用栈模拟递归过程，或者用Morris遍历降低空间复杂度。Morris遍历是一种常用于中序遍历的算法，利用树的右子树的空指针来保存当前节点的前驱节点，从而实现O(1)空间复杂度。这种技巧在处理大规模数据时非常关键。如果题目不涉及节点修改，或者需要保存遍历路径，递归是首选，否则迭代才是出路。

五 二叉树的平衡与旋转是关键点
平衡树和旋转是刷题中绕不过的坎，特别是AVL树和红黑树的实现。我见过很多同学在实现AVL树时，忘记调整高度和旋转操作，导致树结构失衡。例如，在插入节点时，必须判断是否需要左旋或右旋，这涉及到子树的高度差。旋转操作需要调整父节点、子节点和孙子节点的关系，这部分逻辑非常复杂，容易出错。常见的错误包括旋转方向判断错误、高度更新遗漏、无法处理多层旋转等情况。如果题目涉及动态平衡，比如实现一个自平衡的二叉搜索树，必须亲自实现旋转逻辑，而不是依赖框架的API。旋转是保持树性能的关键，必须熟练掌握。

六 层序遍历必须用队列来实现
层序遍历是树操作中最重要的方法之一，必须用队列来实现。我见过很多同学用栈来模拟，结果层次混乱。正确的方式是用一个队列，每次取出队头元素，处理完后再将子节点入队。在Python中可以用deque，这样可以快速从左边弹出元素。比如from collections import deque; q = deque([root]); while q: node = q.popleft(); process(node); if node.left: q.append(node.left); if node.right: q.append(node.right)。这种写法比较直观，但要注意队列的初始化和处理顺序。如果题目需要记录每一层的结果，比如返回每层节点值的列表，必须用一个临时队列或者记录当前队列长度来分层处理。层序遍历的性能直接影响整体解题效率，必须掌握。

七 树的序列化与反序列化要用前序方式
树的序列化和反序列化是面试高频考点，必须用前序方式实现。我见过很多同学用中序或后序写序列化，结果反序列化时无法正确恢复结构。正确的做法是用前序遍历，因为根节点在前，子节点在后，可以确保反序列化时能正确构建树的左右结构。比如Python中可以用前序遍历写成字符串，遇到null用特殊符号表示，如#。反序列化时，用split()分割字符串，并用递归或栈来构建节点。关键点在于在反序列化时，严格按照前序顺序处理，确保每个节点的左右子节点都能被正确还原。如果用迭代方式，必须用队列来处理，否则会陷入无限循环。

八 树的动态规划与DFS结合使用
树的动态规划问题通常需要结合DFS或者BFS来处理，比如LeetCode 124题的最大路径和。我见过很多同学直接写递归，结果无法处理路径的组合问题。正确的做法是用DFS遍历树，同时在每个节点上保存左右子树的最大路径值，并将该值与当前节点的值相加。例如，定义一个递归函数返回当前节点子树的最大路径值，函数内部计算左、右子树的最大值，然后取最大值作为当前节点的贡献。同时，维护一个全局变量来记录整个树的最大路径和。这种写法在Python中非常常见，但要注意避免重复计算，以及如何处理叶子节点的特殊情形。动态规划的关键在于状态转移，必须理解每一步如何保存中间结果。

九 树的后续遍历要规避空指针问题
后续遍历是树算法中最难处理的一种，因为必须等到子节点处理完才能处理当前节点。我见过很多同学在实现后续遍历的时候，因为子节点为null导致逻辑错误。正确的做法是用栈模拟递归过程，或者用Morris遍历。在栈实现中，需要区分访问节点的状态，比如用一个标记表示是否已经处理过该节点。例如，入栈时将节点标记为未处理，处理完再入栈一次，标记为已处理。这样在弹出栈时，如果标记为已处理，就进行操作，否则处理其子节点。这种写法在Python中比较常见，但要注意标记的使用和栈的维护。如果用Morris，需要利用右子树的空指针来构建后续遍历的路径，这虽然复杂，但空间效率更高。

十 树的子结构问题要用递归比对
判断两个树是否是子结构的问题，必须用递归方式逐层比对。我见过很多同学用暴力遍历的方式，结果时间复杂度很高，无法通过大规模数据。正确的做法是，先遍历主树，找到与子树根节点值相同的节点，然后递归比对子树是否匹配。比如在Python中，可以写一个函数isSubStructure(root, subRoot)，其内部使用递归判断每个节点是否与子节点相同。递归函数中要注意，如果当前节点值不匹配，直接返回False，否则继续比对左右子节点。这种写法在LeetCode 572题中非常常见，但必须注意递归的终止条件和边界处理。

十一 树的结构转换要用指针操作
树的结构转换是刷题中常见的操作，比如将二叉树转换为双向链表。我见过很多同学在实现过程中，忘记处理左右指针的指向，导致链表结构混乱。正确的做法是用中序遍历的方式，将每个节点的右指针指向下一个节点，左指针指向None。例如，在Python中，可以定义一个函数将二叉树转换为双向链表，并用全局变量保存前驱节点。在遍历过程中，每个节点的左指针指向前驱，右指针指向下一个节点。这种写法在LeetCode 114题中非常典型，但要注意如何处理空节点，以及如何避免循环引用。

十二 树的搜索与插入要处理重复值
在二叉搜索树中，处理重复值是关键。我见过很多同学在搜索时没有考虑重复值的情况，导致结果错误。正确的做法是，如果允许重复值，插入时可以选择左子树或右子树，而搜索时可以返回所有匹配节点，或者只返回其中一个。比如在Python中，可以写一个函数search(root, val)，函数内部先判断当前节点是否为None，如果是则返回False，否则比较当前节点值，如果相等返回True，否则递归处理左或右子树。在插入过程中，必须根据值的大小决定插入方向，如果值相等，则可以插入到左或右子树，这取决于题目要求。处理重复值的细节很容易被忽略，但这是面试官关注的点。

十三 树的平衡问题要评估时间复杂度
平衡树的实现必须考虑时间复杂度，特别是在插入和删除操作中。我见过很多同学在实现AVL树时，忽略旋转操作的时间复杂度，导致算法效率低下。正确的做法是，每次插入或删除后都要更新高度，并检查平衡因子。如果平衡因子超过1，就需要进行旋转。比如左旋转和右旋转的实现方式，必须确保旋转后的树结构正确。在Python中，可以写一个函数来处理旋转逻辑，并在每次操作后调用该函数。平衡因子的计算方式为当前节点左子树高度减去右子树高度，必须确保每个节点的平衡因子在-1到1之间。如果忽略这些细节，树的性能会急剧下降。

十四 树的链表操作要避免内存泄漏
将树转换为链表时，必须注意内存泄漏问题。我见过很多同学在实现过程中，没有正确释放节点，导致程序占用过多内存，甚至崩溃。正确的做法是，在转换过程中，用指针直接链接，避免不必要的复制。比如在Python中，可以使用指针来操作节点，而不是重新创建对象。如果使用递归方式，必须确保每个节点的处理不会导致内存引用无法释放。在LeetCode 114题中，转换双向链表时需要注意如何处理节点的左右指针，避免形成循环。内存管理在树的链表操作中非常关键，必须手动控制节点的引用。

十五 树的路径问题要理解树的深度
路径问题的难点在于如何找到树中的最长或最短路径。我见过很多同学在处理过程中，忽略树的深度，导致结果错误。正确的做法是，用DFS递归计算每个节点的深度，并保存最大深度值。例如，在Python中，可以写一个函数maxDepth(root)，函数内部递归计算左子树和右子树的深度，并取最大值加一。这种写法在LeetCode 104题中非常常见，但必须注意递归的终止条件，比如当root为None时返回0。如果题目允许路径可以是任意方向，比如从根到叶，或者任意路径，必须用递归方式遍历所有可能的路径，并保存最大值。路径问题的关键在于如何正确传递和保存当前路径的信息。

十六 树的最小高度与最大高度的对比
计算树的最小高度和最大高度是常见的问题，两者在实现上差异很大。我见过很多同学在实现时混淆了两者，导致结果错误。最小高度可以用BFS方式，每次层序遍历到最浅的叶子节点即返回。比如在Python中，用队列保存当前层的所有节点，每层遍历一次，直到遇到叶子节点。而最大高度则可以用DFS，每次递归到最深的节点，取最大值。例如，在Python中，可以写一个函数maxHeight(root)，如果root为None返回0，否则取左子树和右子树的高度最大值加一。这两种方式在LeetCode中都有对应的题目，必须分别掌握。搞混这两者，会导致结果与预期不符。

十七 树的直径问题要用两次DFS
计算树的直径是经典的树算法问题，必须用两次DFS。我见过很多同学在第一次DFS时没有正确计算路径长度，导致结果错误。正确的做法是，先用DFS找到最远节点，再以该节点为起点，用DFS找到另一条最远路径，这两条路径之和就是直径。例如，在Python中，可以定义一个函数findDiameter(root)，该函数内部调用两次depth()函数。第一次depth()返回最远节点的路径长度，第二次depth()返回以该节点为起点的最长路径。这种方法在LeetCode 543题中非常典型，但必须注意如何传递和保存当前节点的路径长度。如果用递归方式，必须确保每次调用都能正确返回当前子树的高度。

十八 树的镜像操作要处理每个子节点
镜像问题的核心在于每个节点的左右子树交换。我见过很多同学在处理过程中，忽略子节点的镜像操作，导致结果错误。正确的做法是，用DFS或BFS遍历树，并在每个节点处交换左右子节点。比如在Python中，可以写一个函数mirrorTree(root)，该函数内部递归交换当前节点的左右子树。如果当前节点为空，直接返回；否则，交换左右子节点，然后递归处理左右子树。这种写法在LeetCode 226题中非常常见，但必须注意递归的终止条件和交换逻辑。如果只交换当前节点的左右子节点，而没处理子树的镜像，会导致整个树结构错误。

十九 树的合并问题要处理左右子树
合并两个树的问题，关键在于如何处理节点的合并。我见过很多同学在合并过程中，没有处理左右子树的合并，导致结果错误。正确的做法是，用DFS遍历两个树，按层处理每个节点。比如在Python中，可以写一个函数mergeTrees(root1, root2)，该函数内部先处理当前节点的值，然后递归合并左右子树。如果其中一个节点为空，就直接使用另一个节点的值。这在LeetCode 617题中非常典型，但必须注意如何处理空节点和递归终止条件。合并后的树结构必须保持原树的结构，同时叠加两个树的值，否则会导致树的形状错误。

二十 树的前缀与后缀处理要递归
树的前缀和后缀操作，比如将树转换为字符串，必须用递归方式处理。我见过很多同学在实现时，没有处理左右子树的前缀或后缀，导致字符串结构错误。正确的做法是，用前序遍历的方式构建字符串，比如根节点值 + 左子树字符串 + 右子树字符串。在Python中，可以写一个函数serialize(root)来生成字符串，如果当前节点为空，返回"null"，否则返回当前值加上左右子树的字符串。这种写法在LeetCode 297题中非常常见，但必须注意如何处理空节点和递归的终止条件。如果只写主节点的值，而忽略子节点的递归，会导致整个序列化失败。