1. 从数组到链式结构为什么二叉树值得我们停下来细看我是在刷到代码随想录算法训练营Day17的时候才真正把二叉树这块硬骨头啃下来的。说实话前面的数组、链表、哈希表、字符串每一章都像是给大脑做了一次扩容但到了二叉树这里感觉完全不一样了——数组和链表是线性的你从头走到尾一条路走到黑就行。二叉树不一样它有了分叉有了左右有了递归这个绕不开的概念。很多人在这一步卡住不是因为题目难而是因为思维还没从迭代切换到递归。我当初也是这样看递归代码觉得挺简单一行调用自己但真让自己写脑子里就一片空白。这篇文章我就想把自己在Day17这一天里从建树到遍历、从深度到BST判定、从满二叉树到完全二叉树的完整学习和排错过程整理出来希望能给正在算法训练营里挣扎的朋友一些参考。1.1 二叉树节点的定义方式在开始写任何二叉树算法之前先把节点的数据结构搞清楚。C里常见的定义是这样struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} };Python的写法更简洁class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right这三个构造函数体其实很有讲究第一个是无参构造第二个是只给值第三个是值、左右孩子一起给。实际刷题的时候我们用得最多的是第二个因为大部分题目的测试用例都是通过数组按层序构造的节点创建时只需要赋值左右孩子后续再挂。要注意一个细节很多人在定义节点时会把左右孩子默认设为NULL但如果你的代码里后续没处理空指针就直接访问node-left-val那必然报错。这一点在二叉树题目里是最大的隐形杀手后面我会专门讲到。1.2 从层序数组到一棵真正的树LeetCode风格的题目输入通常是一个层序遍历的数组比如[3,9,20,null,null,15,7]其中null表示这个位置没有节点。刚开始我看到这种输入很懵这怎么还原成一棵树其实原理不复杂就是用队列做BFS广度优先搜索。根节点先入队然后每次从队列里弹出一个节点就从数组里按顺序取两个值左孩子和右孩子如果值不是null就创建节点并挂上去然后入队。这个过程循环往复直到数组里的元素全部用完。我按照这个思路写了一个建树函数在这里分享出来def build_tree(data): if not data or data[0] is None: return None root TreeNode(data[0]) queue [root] idx 1 while idx len(data): node queue.pop(0) if idx len(data) and data[idx] is not None: node.left TreeNode(data[idx]) queue.append(node.left) idx 1 if idx len(data) and data[idx] is not None: node.right TreeNode(data[idx]) queue.append(node.right) idx 1 return root这个函数的逻辑就是每访问一个父节点就消费掉数组中的两个元素。如果你是初学者我建议你拿[3,9,20,null,null,15,7]这个例子手动走一遍对理解二叉树的结构非常有帮助。2. 三种深度优先遍历的递归模板与迭代改造二叉树的遍历是Day17的重头戏没有之一。前序、中序、后序这三种深度优先遍历看起来只是打印顺序不同但它们背后的递归逻辑和信息利用方式完全不同很多二叉树的高阶算法都建立在这三种遍历之上。2.1 递归遍历的三行代码先看最简单的递归版本。我以前总觉得递归很神秘后来想明白了递归就是在函数里调用自己只不过每次调用时传入的节点不同。前序遍历的递归代码长这样def preorder_traversal(root): if root is None: return [] result [] result.append(root.val) result.extend(preorder_traversal(root.left)) result.extend(preorder_traversal(root.right)) return result中序遍历就是把result.append(root.val)放到中间后序遍历就是放到最后。就这么简单。但你要注意一个关键点递归的终止条件必须是root is None而不是root.left is None。很多第一次写递归的人会在终止条件上犯迷糊结果就是无限递归或者空指针异常。我还记得自己当初第一次写中序遍历把终止条件写成了if root and root.left is None: return [root.val]结果在只有右子树的测试用例上直接崩了。正确做法是先处理空节点的情况然后再递归处理左右子树。2.2 迭代遍历如何用栈模拟递归递归虽然简洁但有些面试场景要求你写出迭代版本因为递归本质上使用系统调用栈当树特别深的时候比如一条链就可能栈溢出。迭代版本需要我们显式地维护一个栈模拟系统调用栈的行为。前序遍历的迭代版本很直观先访问根节点然后因为栈是后进先出所以先压右孩子再压左孩子这样弹出时先访问左孩子顺序才能对得上def preorder_iter(root): if root is None: return [] stack [root] result [] 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中序遍历的迭代写法就要绕一些了。核心思路是先走到最左边再回头访问代码是这样def inorder_iter(root): result [] stack [] cur root while cur or stack: while cur: stack.append(cur) cur cur.left cur stack.pop() result.append(cur.val) cur cur.right return result这套一路向左压栈弹栈后转向右子树的写法我第一次看的时候觉得跟天书一样后来在纸上画了一棵三层的树一步一步走了一遍才真正明白它在干什么。如果你想理解中序遍历的迭代写法一定不要只看代码要自己动手画一画。2.3 层序遍历队列的天然主场深度优先遍历讲完了那层序遍历呢层序就是逐层从左到右遍历这正好契合队列的先进先出特性。代码很直接def level_order(root): if root is None: return [] queue [root] result [] while queue: level_size len(queue) level [] for _ in range(level_size): node queue.pop(0) level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result注意这里有一个关键设计在遍历每一层之前先记录level_size len(queue)然后只处理当前层的节点。如果不这样做队列里会混入下一层的节点层就分不清了。这个技巧在二叉树右视图层平均值等题目里几乎都要用到。3. 二叉树的深度从最大深度到最小深度的坑深度问题是二叉树里特别经典的一类题目也是Day17内容里比较容易出错的环节。3.1 最大深度递归到底层再返回求二叉树的最大深度递归思路非常清晰一棵树的最大深度就是左子树和右子树深度的较大值再加1。代码def max_depth(root): if root is None: return 0 left_depth max_depth(root.left) right_depth max_depth(root.right) return max(left_depth, right_depth) 1你可能觉得这也太简单了吧但我要提醒你一个容易忽略的细节这里加1是加的当前这一层而不是左右子树各自加1。我见过有同学写成return max(left_depth 1, right_depth 1)结果深度全都偏大。原因是左右子树的递归返回结果里已经包含了它们各自的层数当前层只需要额外加一次就行。这个递归你可以这样理解你站在根节点往左走能走3步往右走能走5步那整棵树的最大深度就是5步加你站的这一层一共6层。3.2 最小深度有个最隐蔽的边界最小深度比最大深度坑多了。第一次写的人十有八九会写成这样def min_depth(root): if root is None: return 0 return min(min_depth(root.left), min_depth(root.right)) 1这个写法看起来对称没毛病但实际是错的。考虑一棵只有根节点和右子树的树左子树是空的min_depth(root.left)返回0右子树深度是2min一下是0加1等于1。但正确的答案应该是2因为最小深度是从根节点到最近叶子节点的距离而左子树根本不存在叶子节点。正确写法要排除空子树的情况def min_depth(root): if root is None: return 0 if root.left is None: return min_depth(root.right) 1 if root.right is None: return min_depth(root.left) 1 return min(min_depth(root.left), min_depth(root.right)) 1这个坑建议所有刷二叉树题的人都拿笔记下来。它不是一次性的小坑二叉树相关的很多题目都会用类似逻辑比如找最浅的叶子节点找最近的叶子节点路径等都要注意空子树不能参与计算这个原则。3.3 从深度到平衡树判断深度问题还有一个经典的变身——判断一棵树是否平衡。这里的平衡指的是任意节点的左右子树高度差不超过1。这道题是深度计算的进阶用法def is_balanced(root): def height(root): if root is None: return 0 left_h height(root.left) if left_h -1: return -1 right_h height(root.right) if right_h -1: return -1 if abs(left_h - right_h) 1: return -1 return max(left_h, right_h) 1 return height(root) ! -1核心技巧就是用-1作为已经不满足条件的标记一旦发现不平衡就逐层向上返回-1避免重复计算。这是二叉树题目里很常见的剪枝思想——某个子树已经不行了就没必要再继续探索下去了。4. 搜索二叉树与满二叉树判定边界条件才是重头戏Day17还会碰到的两类判定型题目判断是不是搜索二叉树BST判断是不是满二叉树/完全二叉树。这类题初看跟遍历差不多但实际上是在考察你对二叉树的性质理解得有多深。4.1 BST判定的经典错误只比较当前节点的左右孩子先说说BST的性质对于任意一个节点它的左子树所有节点的值都小于它右子树所有节点的值都大于它。注意是所有节点不只是左孩子和右孩子。很多人的第一版代码长这样def is_valid_bst_wrong(root): if root is None: return True if root.left and root.left.val root.val: return False if root.right and root.right.val root.val: return False return is_valid_bst_wrong(root.left) and is_valid_bst_wrong(root.right)错哪了考虑一棵树根是10右孩子是15右孩子的左孩子是12。按上面的判断10的右孩子15大于10没问题15的左孩子12小于15也没问题。于是返回True。但这不是一棵BST因为12虽然小于15却大于根节点10它出现在右子树里却破坏了全局的BST性质。正确的做法是给每个节点划定一个值域范围递归时把这个范围不断收窄def is_valid_bst(root): def validate(node, low, high): if node is None: return True if node.val low or node.val high: return False return validate(node.left, low, node.val) and validate(node.right, node.val, high) return validate(root, float(-inf), float(inf))这样当递归到某个右子树的左孩子时它的值域被限定在(节点值, 右孩子值)之间任何越界的值都会被拦截。还有一种解法是中序遍历后看结果是否严格递增。BST的中序遍历有一个重要性质结果必然严格递增。但你仍然要小心严格递增中的严格二字也就是说等于也不行。4.2 满二叉树和完全二叉树的区别满二叉树和完全二叉树这两个概念我在GESP六级相关学习材料里也看到过很多同学容易混淆。满二叉树每一层的节点数都是最大值。如果深度为h那么满二叉树的节点总数就是2^h - 1。判断方法很简单如果某个节点没有左孩子但有右孩子就不是满二叉树如果某个节点是叶子节点那它的所有兄弟节点也必须是叶子节点。完全二叉树除最后一层外每一层都是满的并且最后一层的节点都集中在左侧。判断方法可以用层序遍历一旦遇到一个空节点那么它之后的所有节点在层序遍历顺序中都必须是空节点。用代码表达就是def is_complete_tree(root): if root is None: return True queue [root] flag False while queue: node queue.pop(0) if node is None: flag True else: if flag: return False queue.append(node.left) queue.append(node.right) return True注意这里我把None也放进了队列。这个做法很巧妙一旦遇到第一个空节点就把flag置为True后面如果再出现非空节点说明空节点后面还有节点那就不是完全二叉树。4.3 搜索二叉树的删除操作为什么难BST的判断只是入门真正让人头疼的是BST的删除操作。为什么难因为删除一个节点后你还要保持BST的所有性质不变。分三种情况删除叶子节点直接删掉即可。删除只有一个子树的节点用子树顶替它。删除有两个子树的节点用左子树的最大值或右子树的最小值来顶替它。第三种情况最麻烦。我记得自己第一次写删除逻辑时光是想清楚怎么把左子树的最大值节点摘下来就折腾了很久。简单来说可以拿右子树的最小节点替换当前节点然后递归地去右子树中删除那个最小节点。这段逻辑写在代码里大概是def delete_node(root, key): if root is None: return root if key root.val: root.left delete_node(root.left, key) elif key root.val: root.right delete_node(root.right, key) else: if root.left is None: return root.right if root.right is None: return root.left # 找到右子树的最小节点 min_node find_min(root.right) root.val min_node.val root.right delete_node(root.right, min_node.val) return rootBST的删除操作在面试里算中等偏上的难度了如果你Day17的练习时间有限可以先掌握判断和搜索删除操作可以放在后面单独加练。5. Day17刷题排错实录我在二叉树代码里踩过的三个坑说实话前面的章节内容都是理论层面的梳理。真正让我对二叉树算法有实质性突破的是那一下午的排错过程。我把那天踩过的三个最有代表性的坑写下来希望对你有切实的帮助。5.1 空指针异常你以为判空了其实没有那天我在做二叉树的所有路径这道题需要递归收集从根到叶子节点的路径。我写的代码长这样def binary_tree_paths(root): result [] def dfs(node, path): if node is None: result.append(path) return if node.left is None and node.right is None: result.append(path [node.val]) return dfs(node.left, path [node.val]) dfs(node.right, path [node.val]) dfs(root, []) return result看起来逻辑没问题但我一跑测试用例就报错AttributeError: NoneType object has no attribute left。我盯着代码看了半天才意识到问题出在递归的入口当node.left为空时dfs(node.left, ...)会传入一个None然后在下一层函数里第一个if node is None虽然能判断出来但我把None也当成一条路径压进result了而且在后面的判断里没加return防护继续执行就出错了。正确做法是在递归函数入口先判断node is None直接return但不要把空路径加入结果。应该是def dfs(node, path): if node is None: return if node.left is None and node.right is None: result.append(path [node.val]) return dfs(node.left, path [node.val]) dfs(node.right, path [node.val])这个坑的教训是只要你的递归会传入可能为None的节点函数的第一行就必须处理None而且处理完要立即return不能继续往下走。5.2 递归返回值被覆盖没有接住子调用的结果还有一道题是把二叉搜索树转为累加树。累加树的定义是每个节点的值等于原树中大于或等于该节点值的所有节点值之和。BST中大于某节点的节点都在它的右子树和它的一些祖先的右子树里。常规解法是反中序遍历——先右后左的中序遍历时累加。我写的代码def convert_bst(root): total 0 def dfs(node): if node is None: return dfs(node.right) total node.val node.val total dfs(node.left) dfs(root) return root问题来了total在外层函数里是普通变量但Python闭包不会自动把它当成外部变量修改。我在dfs里写total node.val时Python会认为这是一个新的局部变量所以total实际上从未被更新。运行之后每个节点的值都没变。解决方法是把total放进一个可变对象里比如列表或者用nonlocal关键字def convert_bst(root): total 0 def dfs(node): nonlocal total if node is None: return dfs(node.right) total node.val node.val total dfs(node.left) dfs(root) return root这种坑不只出现在二叉树里Python的闭包机制在递归场景下特别容易踩到。如果你用的是C可能没有这个问题但Java里如果是在内部类方法中修改外部变量也会遇到类似限制。写递归时先想清楚变量作用域。5.3 递归顺序理解错前中后序不是打印顺序那么简单最后一个坑是我在一道根据中序和后序遍历序列构造二叉树的题目里踩的。当时我总觉得只要把序列切分正确递归构造就行了。但我忽略了关键一点递归时先构造右子树还是左子树取决于我们用的是后序序列的末尾还是前序序列的开头来找根节点。以中序后序为例后序序列的最后一个元素是根节点。找到根节点后在中序序列里定位它就能确定左子树的长度和右子树的长度。然后在后序序列里从后向前依次是根、右子树根、左子树根。所以递归时应该先递归构造右子树再构造左子树——因为后序序列里越靠后的元素在树中的位置越接近根节点且优先属于右子树。我当时就是因为先递归构造左子树导致后序序列的切割索引完全对不上。排查了很久最后画了棵树才明白代码里的子数组边界处理是一个很容易让人崩溃的活儿。这类构造类题目的通用技巧是不要直接切片而是用索引下标来标记子数组的起止位置。这样既高效又不容易出错。我用两个序列的下标范围写了一个标准解法def build_tree_from_inorder_postorder(inorder, postorder): idx_map {val: i for i, val in enumerate(inorder)} def build(in_left, in_right, post_left, post_right): if post_left post_right: return None root_val postorder[post_right] root TreeNode(root_val) in_root idx_map[root_val] left_size in_root - in_left root.right build(in_root 1, in_right, post_left left_size, post_right - 1) root.left build(in_left, in_root - 1, post_left, post_left left_size - 1) return root return build(0, len(inorder) - 1, 0, len(postorder) - 1)再次强调这类题的索引计算一定要自己画一遍特别是左子树在后序序列里的范围它的起始位置是post_left结束位置是post_left left_size - 1。多算几次你就能形成肌肉记忆。6. 把Day17的知识点串起来从遍历到构造的完整路径到了这里你可能已经掌握了不少零散的知识点但心里还是有点乱遍历、深度、BST判断、满二叉树、构造二叉树这些知识点之间到底是什么关系我学习的时候有个习惯每学完一个章节就把相关的题目按依赖关系排一个序列。Day17的知识点我建议按这样一条路径串起来第一步把遍历写熟。前序、中序、后序、层序递归和迭代两种版本至少要会写一种这是所有后续题目的基础。特别是前序和中序的迭代写法建议多练几遍因为很多高级题目会在迭代过程中做文章。第二步用遍历解决属性问题。深度、平衡、路径、叶子节点个数这类题目本质上都是遍历时记录一些信息所以只要第一步扎实这里会比较顺。第三步用遍历解决性质判断问题。BST判定、完全二叉树判定、满二叉树判定这类题的难点在于什么时候停止判断以及判断条件是什么。它们跟遍历是一回事只是变成在遍历过程中做合规性检查。第四步从序列还原结构。根据前序中序构造二叉树、根据中序后序构造二叉树、把数组转成高度平衡BST等。这类题是所有遍历和性质题的集大成者因为它们要求你倒过来思考知道某种遍历顺序能不能还原树的形状当你把这几步都走一遍Day17的二叉树知识就基本成体系了。以后你再遇到翻转二叉树找最近公共祖先求所有路径这些题目就会发现它们其实都是在遍历的基础上做一点变化而已。模板和套路固然重要但真正值钱的还是你动手画图、手动模拟边界条件的过程。二叉树是很适合可视化学习的数据结构我的建议是每学一个算法至少手画一棵三层以上的树用笔模拟一遍算法流程比直接刷十道题都管用。