1. 二叉树从概念到实战的完整认知在程序员的日常开发中无论是处理文件系统目录、实现数据库索引还是解析复杂的表达式我们总会遇到一种结构它像一棵倒挂的树有根、有枝、有叶每个节点最多只有两个“孩子”。没错这就是二叉树。它远不止是教科书上的一个抽象概念而是构建更复杂数据结构如堆、红黑树、B树和实现高效算法如快速排序、哈夫曼编码的基石。很多朋友初学数据结构时觉得二叉树的理论懂了但一到自己动手实现或者面试被问到“如何判断一棵树是否平衡”、“如何序列化与反序列化”时就有点发懵。这篇文章我就结合自己十多年踩过的坑和积累的经验带你彻底吃透二叉树从最基础的概念到核心操作的代码实现再到那些面试官最爱问的进阶问题我们逐一拆解目标是让你不仅能理解更能写出健壮、高效的二叉树代码。2. 二叉树的核心概念与形态全解析理解二叉树绝不能停留在“一个节点有两个指针”的层面。我们需要深入它的定义、特性和各种具体形态这是后续所有操作和算法的基础。2.1 定义与关键性质一棵二叉树是nn≥0个节点的有限集合。这个集合要么是空集空二叉树要么由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。这个递归定义是理解二叉树一切操作的源头。这里有几个必须刻在脑子里的关键性质它们直接决定了算法的边界和效率第i层最多有 2^(i-1) 个节点根节点算第1层。这个性质来自于二叉树的定义每个节点最多有两个孩子。深度为k的二叉树最多有 2^k - 1 个节点这是等比数列求和的结果。当每一层都满员时总节点数达到最大。对于任何一棵二叉树如果其叶子节点数为 n0度为2的节点数为 n2则 n0 n2 1。这是一个非常重要的性质证明思路是设总节点数为N度为1的节点数为n1则有 N n0 n1 n2。从边的角度考虑总边数为 N-1也等于 n1 2*n2。联立两个等式即可得证。这个性质在分析树结构和一些算法题中非常有用。2.2 两种特殊的二叉树形态在众多形态中有两种二叉树具有极其重要的地位因为它们代表了两种极端的、同时也是最优的结构状态。满二叉树一棵深度为k且有 2^k - 1 个节点的二叉树。顾名思义每一层都“满”了所有节点都有两个子节点除了叶子节点。它是完全二叉树的特例。完全二叉树深度为k的有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时称之为完全二叉树。简单说就是除了最后一层其他层都是满的并且最后一层的节点都尽可能靠左排列。注意完全二叉树这个“从左到右填充”的特性使得它可以用数组来高效存储。对于数组中下标为 i通常从0开始的节点其左孩子下标为2*i 1右孩子为2*i 2父节点下标为(i-1)/2整数除法。这个特性是**堆Heap**这种数据结构得以实现的基础。2.3 二叉树的存储链式与顺序如何把树形的逻辑结构存到线性的内存里主要有两种方式链式存储这是最直观、最常用的方式。我们定义一个节点类包含数据域、左孩子指针、右孩子指针。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right链式存储灵活能方便地表示任意形态的二叉树增删节点容易。但缺点是每个节点需要额外的空间存储指针且访问特定节点如按编号访问不如数组快。顺序存储用一组连续的存储单元数组存放节点。通常这只适用于完全二叉树这样才能利用下标公式快速定位父子节点。对于非完全二叉树为了保持下标对应关系需要将空缺的位置用特殊值如None填充在极端情况下如右斜树会造成大量的空间浪费。实操心得在绝大多数算法题和日常开发中我们默认使用链式存储。顺序存储仅在实现堆等特定结构时使用。当你看到题目给出的树是用列表[1,2,3,4,5,null,6]表示时这其实是完全二叉树的顺序存储表示法你需要能在大脑中将其还原成链式结构。3. 二叉树的遍历深度优先与广度优先遍历即访问树中每个节点且仅访问一次是二叉树所有操作的核心。根据访问根节点的顺序深度优先遍历DFS分为三种经典方式而广度优先遍历BFS则是另一种重要策略。3.1 深度优先遍历的递归实现递归实现简洁优美直接体现了二叉树的递归定义。前序遍历根 - 左 - 右。常用于复制一棵树、计算前缀表达式。def preorder_traversal(root): result [] def traverse(node): if not node: return result.append(node.val) # 访问根节点 traverse(node.left) # 遍历左子树 traverse(node.right) # 遍历右子树 traverse(root) return result中序遍历左 - 根 - 右。对二叉搜索树进行中序遍历能得到一个升序序列。这是它的核心应用。def inorder_traversal(root): result [] def traverse(node): if not node: return traverse(node.left) # 遍历左子树 result.append(node.val) # 访问根节点 traverse(node.right) # 遍历右子树 traverse(root) return result后序遍历左 - 右 - 根。常用于释放二叉树的内存、计算后缀表达式、计算节点的高度。def postorder_traversal(root): result [] def traverse(node): if not node: return traverse(node.left) # 遍历左子树 traverse(node.right) # 遍历右子树 result.append(node.val) # 访问根节点 traverse(root) return result注意事项递归虽然简单但当树非常深例如达到几万层时可能会引发栈溢出错误。这是因为每一层递归调用都会在调用栈上占用空间。在Python中可以通过设置递归深度限制sys.setrecursionlimit()来缓解但根本解决之道是使用迭代法。3.2 深度优先遍历的迭代实现迭代法使用栈来模拟递归调用栈避免了递归的系统开销和栈溢出风险。这是面试中常考的难点。以前序遍历为例其核心思想是将根节点压入栈。循环栈不空时 a. 弹出栈顶节点并访问。 b. 将其右孩子先压栈再压左孩子因为栈是LIFO这样能保证左孩子先被访问。def preorder_traversal_iterative(root): if not root: return [] result [] stack [root] while stack: node stack.pop() result.append(node.val) # 先右后左保证出栈顺序是左先右后 if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result中序遍历的迭代法则略有不同需要一个指针cur来帮助访问节点def inorder_traversal_iterative(root): result [] stack [] cur root while cur or stack: # 一路向左把经过的节点都压入栈 while cur: stack.append(cur) cur cur.left # 此时cur为空弹出栈顶节点这是最左边的节点 cur stack.pop() result.append(cur.val) # 转向右子树 cur cur.right return result后序遍历的迭代法最复杂但可以巧用前序遍历的变体按照“根 - 右 - 左”的顺序遍历然后将结果反转即得到“左 - 右 - 根”的后序结果。def postorder_traversal_iterative(root): if not root: return [] result [] stack [root] while stack: node stack.pop() result.append(node.val) # 先左后右这样出栈顺序就是右先左后反转后就是左右根 if node.left: stack.append(node.left) if node.right: stack.append(node.right) return result[::-1] # 反转结果3.3 广度优先遍历层序遍历层序遍历按照从上到下、从左到右的顺序访问节点使用队列实现。from collections import deque def level_order_traversal(root): if not root: return [] result [] queue deque([root]) while queue: level_size len(queue) current_level [] for _ in range(level_size): node queue.popleft() current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result这段代码不仅实现了层序遍历还将每一层的节点值分别存储在一个子列表中这种格式在很多题目中非常有用。层序遍历是求二叉树深度、宽度、寻找特定层节点等问题的利器。实操心得务必亲手实现这四种遍历的迭代版本。面试时面试官让你写非递归遍历的概率远大于写递归。理解栈和队列在遍历中扮演的角色是理解树形结构算法思想的关键一步。4. 二叉树核心操作与属性判断实战掌握了遍历我们就可以解决二叉树的大部分基础问题。这些问题往往是更复杂算法的基础构件。4.1 基础属性计算计算节点总数递归思想总数 1根节点 左子树节点数 右子树节点数。def count_nodes(root): if not root: return 0 return 1 count_nodes(root.left) count_nodes(root.right)计算叶子节点数叶子节点是没有孩子的节点。递归判断如果是叶子返回1否则返回左右子树叶子数之和。def count_leaves(root): if not root: return 0 if not root.left and not root.right: return 1 return count_leaves(root.left) count_leaves(root.right)计算树的深度/高度树的深度是从根到叶的最长路径上的节点数。树的高度定义类似有时根节点高度为0有时为1需明确。递归计算高度 1 max(左子树高度 右子树高度)。def max_depth(root): if not root: return 0 # 通常定义空树深度为0 left_depth max_depth(root.left) right_depth max_depth(root.right) return max(left_depth, right_depth) 14.2 对称性与平衡性判断判断对称二叉树检查一棵树是否是镜像对称的。递归思想两棵树对称的条件是1. 根节点值相等2. 树A的左子树与树B的右子树对称3. 树A的右子树与树B的左子树对称。对于一棵树本身是否对称可以看作它的左右子树是否镜像。def is_symmetric(root): def check(left, right): # 都为空 if not left and not right: return True # 一个为空一个不为空或值不相等 if not left or not right or left.val ! right.val: return False # 递归检查子树 return check(left.left, right.right) and check(left.right, right.left) return check(root.left, root.right) if root else True判断平衡二叉树平衡二叉树AVL树的基础定义为每个节点的左右两个子树的高度差的绝对值不超过1。这是一个后序遍历的经典应用因为我们需要先知道子树的高度才能判断当前节点是否平衡。def is_balanced(root): def get_height_and_check(node): if not node: return 0, True # 返回高度和是否平衡 left_height, left_balanced get_height_and_check(node.left) right_height, right_balanced get_height_and_check(node.right) current_height max(left_height, right_height) 1 # 当前节点平衡的条件左右子树都平衡且高度差1 current_balanced left_balanced and right_balanced and abs(left_height - right_height) 1 return current_height, current_balanced _, balanced get_height_and_check(root) return balanced这个实现通过一次后序遍历同时计算高度和判断平衡性避免了重复计算时间复杂度为O(N)。4.3 路径与祖先问题寻找从根到叶子的所有路径典型的DFS回溯问题。在遍历过程中记录路径当到达叶子节点时将路径保存。def binary_tree_paths(root): def dfs(node, path, result): if not node: return path.append(str(node.val)) # 如果是叶子节点保存路径 if not node.left and not node.right: result.append(-.join(path)) else: dfs(node.left, path, result) dfs(node.right, path, result) path.pop() # 回溯移除当前节点 result [] dfs(root, [], result) return result寻找两个节点的最近公共祖先这是一个高频面试题。思路是后序遍历从底向上返回信息。如果当前节点是p或q则返回当前节点。递归查询左右子树。如果左右子树返回值都不为空说明p和q分布在当前节点两侧当前节点就是LCA。如果一边为空则LCA在另一边。def lowest_common_ancestor(root, p, q): if not root or root p or root q: return root left lowest_common_ancestor(root.left, p, q) right lowest_common_ancestor(root.right, p, q) if left and right: # p和q分布在两侧 return root # 否则LCA在非空的那一侧 return left if left else right5. 二叉搜索树有序性的力量二叉搜索树是一种特殊的二叉树它满足对于任意节点其左子树所有节点的值都小于该节点的值其右子树所有节点的值都大于该节点的值。这个性质带来了高效的查找、插入和删除操作平均O(logN)。5.1 BST的查找、插入与删除查找类似于二分查找根据目标值与当前节点值的大小关系决定向左子树还是右子树搜索。def search_bst(root, val): cur root while cur: if cur.val val: return cur elif cur.val val: cur cur.left else: cur cur.right return None # 未找到插入先找到合适的插入位置一个空位然后创建新节点插入。注意保持BST性质。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) # val root.val 的情况根据具体需求决定如不允许重复则直接返回 return root删除这是BST操作中最复杂的一环需要分三种情况处理要删除的节点是叶子节点直接删除。要删除的节点只有一个子节点用其子节点替代自己。要删除的节点有两个子节点找到其中序遍历的前驱节点左子树的最大值或后继节点右子树的最小值用这个节点的值替换要删除的节点的值然后递归删除那个前驱或后继节点它必定是情况1或2。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: # 找到要删除的节点 # 情况1 2: 有一个子节点或没有子节点 if not root.left: return root.right if not root.right: return root.left # 情况3: 有两个子节点找后继节点右子树的最小节点 successor root.right while successor.left: successor successor.left # 用后继节点的值替换当前节点值 root.val successor.val # 删除后继节点它现在在右子树里 root.right delete_node(root.right, successor.val) return root5.2 BST的验证与转换验证BST不能只简单地检查一个节点是否大于左孩子且小于右孩子因为需要保证整个左子树都小于节点。正确的方法是使用中序遍历检查遍历序列是否严格递增。或者使用递归传递当前节点值的上下界。def is_valid_bst(root): def check(node, lowerfloat(-inf), upperfloat(inf)): if not node: return True val node.val if val lower or val upper: return False # 左子树的所有节点值必须小于val右子树必须大于val return (check(node.left, lower, val) and check(node.right, val, upper)) return check(root)有序数组构造BST为了构造一棵高度平衡的BST我们可以每次取数组中间的元素作为根节点递归构造左右子树。def sorted_array_to_bst(nums): def helper(left, right): if left right: return None mid (left right) // 2 root TreeNode(nums[mid]) root.left helper(left, mid - 1) root.right helper(mid 1, right) return root return helper(0, len(nums) - 1)6. 二叉树序列化与反序列化如何将一棵二叉树转换成字符串以便存储或传输以及如何从字符串重建二叉树这是一个非常实际的问题。LeetCode的树形题目通常就用这种方式给出输入。6.1 前序遍历序列化与反序列化前序遍历的顺序非常适合序列化。我们用特殊字符如“#”表示空节点用分隔符如“,”分隔节点值。def serialize(root): Encodes a tree to a single string. def dfs(node): if not node: return [#] return [str(node.val)] dfs(node.left) dfs(node.right) return ,.join(dfs(root)) def deserialize(data): Decodes your encoded data to tree. vals iter(data.split(,)) # 使用迭代器方便按顺序取 def dfs(): val next(vals) if val #: return None node TreeNode(int(val)) node.left dfs() node.right dfs() return node return dfs()序列化结果类似“1,2,#,#,3,4,#,#,5,#,#”。反序列化时按照前序的顺序递归构建即可。6.2 层序遍历序列化与反序列化层序遍历的序列化结果更直观与LeetCode的表示法一致。from collections import deque def serialize_level(root): if not root: return queue deque([root]) result [] while queue: node queue.popleft() if node: result.append(str(node.val)) queue.append(node.left) queue.append(node.right) else: result.append(#) # 去掉末尾连续的“#”它们代表最后一层的空节点 while result and result[-1] #: result.pop() return ,.join(result) def deserialize_level(data): if not data: return None vals data.split(,) root TreeNode(int(vals[0])) queue deque([root]) i 1 # 指针指向待处理的子节点值 while queue and i len(vals): node queue.popleft() # 构建左孩子 if vals[i] ! #: node.left TreeNode(int(vals[i])) queue.append(node.left) i 1 # 构建右孩子 if i len(vals) and vals[i] ! #: node.right TreeNode(int(vals[i])) queue.append(node.right) i 1 return root注意事项序列化时选择哪种方式取决于需求。前序/后序的序列化字符串更紧凑但层序的序列化结果人类可读性更好且能直接看出树的结构。反序列化的关键是序列化和反序列化必须使用同一种遍历顺序。7. 二叉树进阶问题与优化技巧当基础问题掌握后面试和实际应用中会遇到一些需要组合技巧或优化思维的题目。7.1 路径总和问题路径总和 I判断是否存在从根到叶子的路径其节点值之和等于目标和。DFS递归到达叶子时判断。def has_path_sum(root, targetSum): if not root: return False # 如果是叶子节点判断剩余值是否等于节点值 if not root.left and not root.right: return targetSum root.val # 否则减去当前值递归判断左右子树 remaining targetSum - root.val return has_path_sum(root.left, remaining) or has_path_sum(root.right, remaining)路径总和 II找出所有满足条件的路径。需要回溯记录路径。def path_sum_ii(root, targetSum): def dfs(node, remaining, path, result): if not node: return path.append(node.val) remaining - node.val if not node.left and not node.right and remaining 0: result.append(path[:]) # 注意添加副本 dfs(node.left, remaining, path, result) dfs(node.right, remaining, path, result) path.pop() # 回溯 result [] dfs(root, targetSum, [], result) return result路径总和 III路径不需要从根开始也不需要在叶子结束但方向必须向下。这是难题。一个直观但低效的方法是双重递归以每个节点为起点向下搜索。高效解法是使用前缀和思想类似数组的连续子数组和问题利用哈希表记录从根到当前节点的路径上各个前缀和出现的次数。def path_sum_iii(root, targetSum): from collections import defaultdict prefix_sum_count defaultdict(int) prefix_sum_count[0] 1 # 重要初始前缀和为0的路径有1条空路径 count 0 def dfs(node, current_sum): nonlocal count if not node: return current_sum node.val # 核心如果存在一个历史前缀和 prev_sum 使得 current_sum - prev_sum targetSum # 即 prev_sum current_sum - targetSum那么从 prev_sum对应的节点之后到当前节点的路径和就是target count prefix_sum_count[current_sum - targetSum] # 将当前前缀和加入记录 prefix_sum_count[current_sum] 1 # 递归处理子节点 dfs(node.left, current_sum) dfs(node.right, current_sum) # 回溯离开当前节点时需要将当前前缀和的计数减1 prefix_sum_count[current_sum] - 1 dfs(root, 0) return count7.2 树的直径与最大路径和二叉树的直径任意两个节点间最长路径的长度边数。这条路径可能不经过根节点。思路对于每个节点经过它的最长路径长度 左子树高度 右子树高度。在计算高度的递归过程中同时更新这个最大值。def diameter_of_binary_tree(root): diameter 0 def depth(node): nonlocal diameter if not node: return 0 left_depth depth(node.left) right_depth depth(node.right) # 更新直径经过当前节点的路径长度 diameter max(diameter, left_depth right_depth) # 返回当前节点的高度 return max(left_depth, right_depth) 1 depth(root) return diameter二叉树中的最大路径和路径和定义为路径上所有节点值之和。路径至少包含一个节点且不一定经过根。这是LeetCode Hard题目。思路类似直径但需要考虑节点值可能为负数。对于每个节点我们计算两个值1) 以该节点为终点的向下最大路径和可向左或向右延伸2) 经过该节点的最大路径和左右自身。用全局变量记录最大值。def max_path_sum(root): max_sum float(-inf) def gain_from_subtree(node): nonlocal max_sum if not node: return 0 # 左右子树提供的最大贡献值如果是负数则舍弃不选 left_gain max(gain_from_subtree(node.left), 0) right_gain max(gain_from_subtree(node.right), 0) # 经过当前节点的最大路径和 price_newpath node.val left_gain right_gain max_sum max(max_sum, price_newpath) # 返回以当前节点为终点的最大路径和只能选择一边 return node.val max(left_gain, right_gain) gain_from_subtree(root) return max_sum7.3 迭代遍历的统一写法与Morris遍历迭代遍历的统一写法前述三种DFS迭代写法各不相同尤其是中序比较别扭。有一种使用栈的通用写法通过将访问的节点和要处理的节点都放入栈中并放入空节点作为标记。这种方法代码风格统一易于理解和记忆。def inorder_unified(root): result [] stack [] if root: stack.append(root) while stack: node stack.pop() if node is not None: # 添加右、中、左节点因为栈是LIFO所以入栈顺序与遍历顺序相反 if node.right: stack.append(node.right) stack.append(node) # 中间节点 stack.append(None) # 标记表示该节点待处理 if node.left: stack.append(node.left) else: # 遇到空标记处理下一个栈顶节点 node stack.pop() result.append(node.val) return result将入栈顺序稍作调整即可改为前序或后序。Morris遍历一种时间复杂度O(N)空间复杂度O(1)的神奇遍历算法。它利用树中大量的空指针在遍历的过程中临时修改树的结构遍历完成后恢复以达到节省空间的目的。其核心思想是找到当前节点的前驱节点中序遍历下的前一个节点。如果当前节点没有左孩子则访问当前节点然后转向右孩子。如果当前节点有左孩子则找到当前节点在中序遍历下的前驱节点即左子树中最右边的节点。如果前驱节点的右指针为空将其指向当前节点建立临时链接然后当前节点向左孩子移动。如果前驱节点的右指针指向当前节点说明左子树已遍历完则断开链接访问当前节点然后当前节点向右孩子移动。 由于代码相对复杂且容易出错除非对空间有极端要求否则在面试和工程中使用递归或显式栈的迭代法更为稳妥。实操心得对于99%的场景掌握递归和基于栈/队列的迭代法已经完全足够。Morris遍历可以作为知识拓展展示你对算法的深入理解但不必强求在短时间内写出完全正确的代码。重点是把递归和迭代的经典写法练到肌肉记忆并能清晰解释其时间和空间复杂度。
二叉树从入门到精通：核心概念、遍历算法与实战应用全解析
1. 二叉树从概念到实战的完整认知在程序员的日常开发中无论是处理文件系统目录、实现数据库索引还是解析复杂的表达式我们总会遇到一种结构它像一棵倒挂的树有根、有枝、有叶每个节点最多只有两个“孩子”。没错这就是二叉树。它远不止是教科书上的一个抽象概念而是构建更复杂数据结构如堆、红黑树、B树和实现高效算法如快速排序、哈夫曼编码的基石。很多朋友初学数据结构时觉得二叉树的理论懂了但一到自己动手实现或者面试被问到“如何判断一棵树是否平衡”、“如何序列化与反序列化”时就有点发懵。这篇文章我就结合自己十多年踩过的坑和积累的经验带你彻底吃透二叉树从最基础的概念到核心操作的代码实现再到那些面试官最爱问的进阶问题我们逐一拆解目标是让你不仅能理解更能写出健壮、高效的二叉树代码。2. 二叉树的核心概念与形态全解析理解二叉树绝不能停留在“一个节点有两个指针”的层面。我们需要深入它的定义、特性和各种具体形态这是后续所有操作和算法的基础。2.1 定义与关键性质一棵二叉树是nn≥0个节点的有限集合。这个集合要么是空集空二叉树要么由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。这个递归定义是理解二叉树一切操作的源头。这里有几个必须刻在脑子里的关键性质它们直接决定了算法的边界和效率第i层最多有 2^(i-1) 个节点根节点算第1层。这个性质来自于二叉树的定义每个节点最多有两个孩子。深度为k的二叉树最多有 2^k - 1 个节点这是等比数列求和的结果。当每一层都满员时总节点数达到最大。对于任何一棵二叉树如果其叶子节点数为 n0度为2的节点数为 n2则 n0 n2 1。这是一个非常重要的性质证明思路是设总节点数为N度为1的节点数为n1则有 N n0 n1 n2。从边的角度考虑总边数为 N-1也等于 n1 2*n2。联立两个等式即可得证。这个性质在分析树结构和一些算法题中非常有用。2.2 两种特殊的二叉树形态在众多形态中有两种二叉树具有极其重要的地位因为它们代表了两种极端的、同时也是最优的结构状态。满二叉树一棵深度为k且有 2^k - 1 个节点的二叉树。顾名思义每一层都“满”了所有节点都有两个子节点除了叶子节点。它是完全二叉树的特例。完全二叉树深度为k的有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时称之为完全二叉树。简单说就是除了最后一层其他层都是满的并且最后一层的节点都尽可能靠左排列。注意完全二叉树这个“从左到右填充”的特性使得它可以用数组来高效存储。对于数组中下标为 i通常从0开始的节点其左孩子下标为2*i 1右孩子为2*i 2父节点下标为(i-1)/2整数除法。这个特性是**堆Heap**这种数据结构得以实现的基础。2.3 二叉树的存储链式与顺序如何把树形的逻辑结构存到线性的内存里主要有两种方式链式存储这是最直观、最常用的方式。我们定义一个节点类包含数据域、左孩子指针、右孩子指针。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right链式存储灵活能方便地表示任意形态的二叉树增删节点容易。但缺点是每个节点需要额外的空间存储指针且访问特定节点如按编号访问不如数组快。顺序存储用一组连续的存储单元数组存放节点。通常这只适用于完全二叉树这样才能利用下标公式快速定位父子节点。对于非完全二叉树为了保持下标对应关系需要将空缺的位置用特殊值如None填充在极端情况下如右斜树会造成大量的空间浪费。实操心得在绝大多数算法题和日常开发中我们默认使用链式存储。顺序存储仅在实现堆等特定结构时使用。当你看到题目给出的树是用列表[1,2,3,4,5,null,6]表示时这其实是完全二叉树的顺序存储表示法你需要能在大脑中将其还原成链式结构。3. 二叉树的遍历深度优先与广度优先遍历即访问树中每个节点且仅访问一次是二叉树所有操作的核心。根据访问根节点的顺序深度优先遍历DFS分为三种经典方式而广度优先遍历BFS则是另一种重要策略。3.1 深度优先遍历的递归实现递归实现简洁优美直接体现了二叉树的递归定义。前序遍历根 - 左 - 右。常用于复制一棵树、计算前缀表达式。def preorder_traversal(root): result [] def traverse(node): if not node: return result.append(node.val) # 访问根节点 traverse(node.left) # 遍历左子树 traverse(node.right) # 遍历右子树 traverse(root) return result中序遍历左 - 根 - 右。对二叉搜索树进行中序遍历能得到一个升序序列。这是它的核心应用。def inorder_traversal(root): result [] def traverse(node): if not node: return traverse(node.left) # 遍历左子树 result.append(node.val) # 访问根节点 traverse(node.right) # 遍历右子树 traverse(root) return result后序遍历左 - 右 - 根。常用于释放二叉树的内存、计算后缀表达式、计算节点的高度。def postorder_traversal(root): result [] def traverse(node): if not node: return traverse(node.left) # 遍历左子树 traverse(node.right) # 遍历右子树 result.append(node.val) # 访问根节点 traverse(root) return result注意事项递归虽然简单但当树非常深例如达到几万层时可能会引发栈溢出错误。这是因为每一层递归调用都会在调用栈上占用空间。在Python中可以通过设置递归深度限制sys.setrecursionlimit()来缓解但根本解决之道是使用迭代法。3.2 深度优先遍历的迭代实现迭代法使用栈来模拟递归调用栈避免了递归的系统开销和栈溢出风险。这是面试中常考的难点。以前序遍历为例其核心思想是将根节点压入栈。循环栈不空时 a. 弹出栈顶节点并访问。 b. 将其右孩子先压栈再压左孩子因为栈是LIFO这样能保证左孩子先被访问。def preorder_traversal_iterative(root): if not root: return [] result [] stack [root] while stack: node stack.pop() result.append(node.val) # 先右后左保证出栈顺序是左先右后 if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result中序遍历的迭代法则略有不同需要一个指针cur来帮助访问节点def inorder_traversal_iterative(root): result [] stack [] cur root while cur or stack: # 一路向左把经过的节点都压入栈 while cur: stack.append(cur) cur cur.left # 此时cur为空弹出栈顶节点这是最左边的节点 cur stack.pop() result.append(cur.val) # 转向右子树 cur cur.right return result后序遍历的迭代法最复杂但可以巧用前序遍历的变体按照“根 - 右 - 左”的顺序遍历然后将结果反转即得到“左 - 右 - 根”的后序结果。def postorder_traversal_iterative(root): if not root: return [] result [] stack [root] while stack: node stack.pop() result.append(node.val) # 先左后右这样出栈顺序就是右先左后反转后就是左右根 if node.left: stack.append(node.left) if node.right: stack.append(node.right) return result[::-1] # 反转结果3.3 广度优先遍历层序遍历层序遍历按照从上到下、从左到右的顺序访问节点使用队列实现。from collections import deque def level_order_traversal(root): if not root: return [] result [] queue deque([root]) while queue: level_size len(queue) current_level [] for _ in range(level_size): node queue.popleft() current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result这段代码不仅实现了层序遍历还将每一层的节点值分别存储在一个子列表中这种格式在很多题目中非常有用。层序遍历是求二叉树深度、宽度、寻找特定层节点等问题的利器。实操心得务必亲手实现这四种遍历的迭代版本。面试时面试官让你写非递归遍历的概率远大于写递归。理解栈和队列在遍历中扮演的角色是理解树形结构算法思想的关键一步。4. 二叉树核心操作与属性判断实战掌握了遍历我们就可以解决二叉树的大部分基础问题。这些问题往往是更复杂算法的基础构件。4.1 基础属性计算计算节点总数递归思想总数 1根节点 左子树节点数 右子树节点数。def count_nodes(root): if not root: return 0 return 1 count_nodes(root.left) count_nodes(root.right)计算叶子节点数叶子节点是没有孩子的节点。递归判断如果是叶子返回1否则返回左右子树叶子数之和。def count_leaves(root): if not root: return 0 if not root.left and not root.right: return 1 return count_leaves(root.left) count_leaves(root.right)计算树的深度/高度树的深度是从根到叶的最长路径上的节点数。树的高度定义类似有时根节点高度为0有时为1需明确。递归计算高度 1 max(左子树高度 右子树高度)。def max_depth(root): if not root: return 0 # 通常定义空树深度为0 left_depth max_depth(root.left) right_depth max_depth(root.right) return max(left_depth, right_depth) 14.2 对称性与平衡性判断判断对称二叉树检查一棵树是否是镜像对称的。递归思想两棵树对称的条件是1. 根节点值相等2. 树A的左子树与树B的右子树对称3. 树A的右子树与树B的左子树对称。对于一棵树本身是否对称可以看作它的左右子树是否镜像。def is_symmetric(root): def check(left, right): # 都为空 if not left and not right: return True # 一个为空一个不为空或值不相等 if not left or not right or left.val ! right.val: return False # 递归检查子树 return check(left.left, right.right) and check(left.right, right.left) return check(root.left, root.right) if root else True判断平衡二叉树平衡二叉树AVL树的基础定义为每个节点的左右两个子树的高度差的绝对值不超过1。这是一个后序遍历的经典应用因为我们需要先知道子树的高度才能判断当前节点是否平衡。def is_balanced(root): def get_height_and_check(node): if not node: return 0, True # 返回高度和是否平衡 left_height, left_balanced get_height_and_check(node.left) right_height, right_balanced get_height_and_check(node.right) current_height max(left_height, right_height) 1 # 当前节点平衡的条件左右子树都平衡且高度差1 current_balanced left_balanced and right_balanced and abs(left_height - right_height) 1 return current_height, current_balanced _, balanced get_height_and_check(root) return balanced这个实现通过一次后序遍历同时计算高度和判断平衡性避免了重复计算时间复杂度为O(N)。4.3 路径与祖先问题寻找从根到叶子的所有路径典型的DFS回溯问题。在遍历过程中记录路径当到达叶子节点时将路径保存。def binary_tree_paths(root): def dfs(node, path, result): if not node: return path.append(str(node.val)) # 如果是叶子节点保存路径 if not node.left and not node.right: result.append(-.join(path)) else: dfs(node.left, path, result) dfs(node.right, path, result) path.pop() # 回溯移除当前节点 result [] dfs(root, [], result) return result寻找两个节点的最近公共祖先这是一个高频面试题。思路是后序遍历从底向上返回信息。如果当前节点是p或q则返回当前节点。递归查询左右子树。如果左右子树返回值都不为空说明p和q分布在当前节点两侧当前节点就是LCA。如果一边为空则LCA在另一边。def lowest_common_ancestor(root, p, q): if not root or root p or root q: return root left lowest_common_ancestor(root.left, p, q) right lowest_common_ancestor(root.right, p, q) if left and right: # p和q分布在两侧 return root # 否则LCA在非空的那一侧 return left if left else right5. 二叉搜索树有序性的力量二叉搜索树是一种特殊的二叉树它满足对于任意节点其左子树所有节点的值都小于该节点的值其右子树所有节点的值都大于该节点的值。这个性质带来了高效的查找、插入和删除操作平均O(logN)。5.1 BST的查找、插入与删除查找类似于二分查找根据目标值与当前节点值的大小关系决定向左子树还是右子树搜索。def search_bst(root, val): cur root while cur: if cur.val val: return cur elif cur.val val: cur cur.left else: cur cur.right return None # 未找到插入先找到合适的插入位置一个空位然后创建新节点插入。注意保持BST性质。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) # val root.val 的情况根据具体需求决定如不允许重复则直接返回 return root删除这是BST操作中最复杂的一环需要分三种情况处理要删除的节点是叶子节点直接删除。要删除的节点只有一个子节点用其子节点替代自己。要删除的节点有两个子节点找到其中序遍历的前驱节点左子树的最大值或后继节点右子树的最小值用这个节点的值替换要删除的节点的值然后递归删除那个前驱或后继节点它必定是情况1或2。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: # 找到要删除的节点 # 情况1 2: 有一个子节点或没有子节点 if not root.left: return root.right if not root.right: return root.left # 情况3: 有两个子节点找后继节点右子树的最小节点 successor root.right while successor.left: successor successor.left # 用后继节点的值替换当前节点值 root.val successor.val # 删除后继节点它现在在右子树里 root.right delete_node(root.right, successor.val) return root5.2 BST的验证与转换验证BST不能只简单地检查一个节点是否大于左孩子且小于右孩子因为需要保证整个左子树都小于节点。正确的方法是使用中序遍历检查遍历序列是否严格递增。或者使用递归传递当前节点值的上下界。def is_valid_bst(root): def check(node, lowerfloat(-inf), upperfloat(inf)): if not node: return True val node.val if val lower or val upper: return False # 左子树的所有节点值必须小于val右子树必须大于val return (check(node.left, lower, val) and check(node.right, val, upper)) return check(root)有序数组构造BST为了构造一棵高度平衡的BST我们可以每次取数组中间的元素作为根节点递归构造左右子树。def sorted_array_to_bst(nums): def helper(left, right): if left right: return None mid (left right) // 2 root TreeNode(nums[mid]) root.left helper(left, mid - 1) root.right helper(mid 1, right) return root return helper(0, len(nums) - 1)6. 二叉树序列化与反序列化如何将一棵二叉树转换成字符串以便存储或传输以及如何从字符串重建二叉树这是一个非常实际的问题。LeetCode的树形题目通常就用这种方式给出输入。6.1 前序遍历序列化与反序列化前序遍历的顺序非常适合序列化。我们用特殊字符如“#”表示空节点用分隔符如“,”分隔节点值。def serialize(root): Encodes a tree to a single string. def dfs(node): if not node: return [#] return [str(node.val)] dfs(node.left) dfs(node.right) return ,.join(dfs(root)) def deserialize(data): Decodes your encoded data to tree. vals iter(data.split(,)) # 使用迭代器方便按顺序取 def dfs(): val next(vals) if val #: return None node TreeNode(int(val)) node.left dfs() node.right dfs() return node return dfs()序列化结果类似“1,2,#,#,3,4,#,#,5,#,#”。反序列化时按照前序的顺序递归构建即可。6.2 层序遍历序列化与反序列化层序遍历的序列化结果更直观与LeetCode的表示法一致。from collections import deque def serialize_level(root): if not root: return queue deque([root]) result [] while queue: node queue.popleft() if node: result.append(str(node.val)) queue.append(node.left) queue.append(node.right) else: result.append(#) # 去掉末尾连续的“#”它们代表最后一层的空节点 while result and result[-1] #: result.pop() return ,.join(result) def deserialize_level(data): if not data: return None vals data.split(,) root TreeNode(int(vals[0])) queue deque([root]) i 1 # 指针指向待处理的子节点值 while queue and i len(vals): node queue.popleft() # 构建左孩子 if vals[i] ! #: node.left TreeNode(int(vals[i])) queue.append(node.left) i 1 # 构建右孩子 if i len(vals) and vals[i] ! #: node.right TreeNode(int(vals[i])) queue.append(node.right) i 1 return root注意事项序列化时选择哪种方式取决于需求。前序/后序的序列化字符串更紧凑但层序的序列化结果人类可读性更好且能直接看出树的结构。反序列化的关键是序列化和反序列化必须使用同一种遍历顺序。7. 二叉树进阶问题与优化技巧当基础问题掌握后面试和实际应用中会遇到一些需要组合技巧或优化思维的题目。7.1 路径总和问题路径总和 I判断是否存在从根到叶子的路径其节点值之和等于目标和。DFS递归到达叶子时判断。def has_path_sum(root, targetSum): if not root: return False # 如果是叶子节点判断剩余值是否等于节点值 if not root.left and not root.right: return targetSum root.val # 否则减去当前值递归判断左右子树 remaining targetSum - root.val return has_path_sum(root.left, remaining) or has_path_sum(root.right, remaining)路径总和 II找出所有满足条件的路径。需要回溯记录路径。def path_sum_ii(root, targetSum): def dfs(node, remaining, path, result): if not node: return path.append(node.val) remaining - node.val if not node.left and not node.right and remaining 0: result.append(path[:]) # 注意添加副本 dfs(node.left, remaining, path, result) dfs(node.right, remaining, path, result) path.pop() # 回溯 result [] dfs(root, targetSum, [], result) return result路径总和 III路径不需要从根开始也不需要在叶子结束但方向必须向下。这是难题。一个直观但低效的方法是双重递归以每个节点为起点向下搜索。高效解法是使用前缀和思想类似数组的连续子数组和问题利用哈希表记录从根到当前节点的路径上各个前缀和出现的次数。def path_sum_iii(root, targetSum): from collections import defaultdict prefix_sum_count defaultdict(int) prefix_sum_count[0] 1 # 重要初始前缀和为0的路径有1条空路径 count 0 def dfs(node, current_sum): nonlocal count if not node: return current_sum node.val # 核心如果存在一个历史前缀和 prev_sum 使得 current_sum - prev_sum targetSum # 即 prev_sum current_sum - targetSum那么从 prev_sum对应的节点之后到当前节点的路径和就是target count prefix_sum_count[current_sum - targetSum] # 将当前前缀和加入记录 prefix_sum_count[current_sum] 1 # 递归处理子节点 dfs(node.left, current_sum) dfs(node.right, current_sum) # 回溯离开当前节点时需要将当前前缀和的计数减1 prefix_sum_count[current_sum] - 1 dfs(root, 0) return count7.2 树的直径与最大路径和二叉树的直径任意两个节点间最长路径的长度边数。这条路径可能不经过根节点。思路对于每个节点经过它的最长路径长度 左子树高度 右子树高度。在计算高度的递归过程中同时更新这个最大值。def diameter_of_binary_tree(root): diameter 0 def depth(node): nonlocal diameter if not node: return 0 left_depth depth(node.left) right_depth depth(node.right) # 更新直径经过当前节点的路径长度 diameter max(diameter, left_depth right_depth) # 返回当前节点的高度 return max(left_depth, right_depth) 1 depth(root) return diameter二叉树中的最大路径和路径和定义为路径上所有节点值之和。路径至少包含一个节点且不一定经过根。这是LeetCode Hard题目。思路类似直径但需要考虑节点值可能为负数。对于每个节点我们计算两个值1) 以该节点为终点的向下最大路径和可向左或向右延伸2) 经过该节点的最大路径和左右自身。用全局变量记录最大值。def max_path_sum(root): max_sum float(-inf) def gain_from_subtree(node): nonlocal max_sum if not node: return 0 # 左右子树提供的最大贡献值如果是负数则舍弃不选 left_gain max(gain_from_subtree(node.left), 0) right_gain max(gain_from_subtree(node.right), 0) # 经过当前节点的最大路径和 price_newpath node.val left_gain right_gain max_sum max(max_sum, price_newpath) # 返回以当前节点为终点的最大路径和只能选择一边 return node.val max(left_gain, right_gain) gain_from_subtree(root) return max_sum7.3 迭代遍历的统一写法与Morris遍历迭代遍历的统一写法前述三种DFS迭代写法各不相同尤其是中序比较别扭。有一种使用栈的通用写法通过将访问的节点和要处理的节点都放入栈中并放入空节点作为标记。这种方法代码风格统一易于理解和记忆。def inorder_unified(root): result [] stack [] if root: stack.append(root) while stack: node stack.pop() if node is not None: # 添加右、中、左节点因为栈是LIFO所以入栈顺序与遍历顺序相反 if node.right: stack.append(node.right) stack.append(node) # 中间节点 stack.append(None) # 标记表示该节点待处理 if node.left: stack.append(node.left) else: # 遇到空标记处理下一个栈顶节点 node stack.pop() result.append(node.val) return result将入栈顺序稍作调整即可改为前序或后序。Morris遍历一种时间复杂度O(N)空间复杂度O(1)的神奇遍历算法。它利用树中大量的空指针在遍历的过程中临时修改树的结构遍历完成后恢复以达到节省空间的目的。其核心思想是找到当前节点的前驱节点中序遍历下的前一个节点。如果当前节点没有左孩子则访问当前节点然后转向右孩子。如果当前节点有左孩子则找到当前节点在中序遍历下的前驱节点即左子树中最右边的节点。如果前驱节点的右指针为空将其指向当前节点建立临时链接然后当前节点向左孩子移动。如果前驱节点的右指针指向当前节点说明左子树已遍历完则断开链接访问当前节点然后当前节点向右孩子移动。 由于代码相对复杂且容易出错除非对空间有极端要求否则在面试和工程中使用递归或显式栈的迭代法更为稳妥。实操心得对于99%的场景掌握递归和基于栈/队列的迭代法已经完全足够。Morris遍历可以作为知识拓展展示你对算法的深入理解但不必强求在短时间内写出完全正确的代码。重点是把递归和迭代的经典写法练到肌肉记忆并能清晰解释其时间和空间复杂度。
