1. 从一道经典题说起为什么求结点层次值得单独拎出来讲但凡刷过二叉树相关题目的人大概率都见过这道题给一棵二叉树再给一个目标结点问这个结点在第几层。很多人第一反应是这不就是遍历的时候顺手记一下深度吗然后五分钟写完递归提交过了关掉页面。但如果你真的在项目里遇到过类似需求——比如组织架构树里查某个员工的汇报层级、文件目录树里定位某个节点的路径深度、权限树里判断某个角色挂载在第几层——你就会发现这道题远没有想象中那么简单。它表面上考的是遍历实际上考的是你对递归返回值语义的理解、对层次定义的边界把控、以及对找不到结点时怎么办这种异常分支的处理。我见过太多人写出来的代码在根结点算第0层还是第1层这个问题上跟需求方扯皮也见过有人递归写成了找到就返回深度找不到返回0结果目标结点恰好在第0层时直接翻车。这篇内容就是围绕计算二叉树中指定结点所在的层次这一个点把能踩的坑、能优化的写法、能延伸的场景全部摊开讲清楚。不管你是刚开始学数据结构的学生还是工作中需要处理树形数据的开发者都能从里面拿到可以直接用的东西。核心关键词就三个二叉树遍历、结点层次计算、递归与迭代实现。我会从层次的定义讲起把递归和迭代两套方案都写透再补上工程里真正会遇到的多叉树、带父指针、大规模数据这些变体。先说结论这道题的最优解不是唯一的递归写法最简洁但有栈溢出风险迭代写法BFS最稳但需要额外队列空间带父指针的写法最快但依赖数据结构本身。选哪种取决于你的树有多大、结构长什么样、调用频率有多高。下面逐个拆。2. 先把层次这个词定义清楚否则后面全是坑2.1 根结点到底算第0层还是第1层这是所有争议的源头。在计算机科学里树的深度depth通常从0开始计根结点的深度是0但在很多业务场景和教材里根结点被称作第一层。这两种定义没有对错只有约定不同但如果你不提前跟需求方对齐代码写完就是白写。我的建议是在函数内部统一用0基根为第0层来计算在返回给业务层时再决定要不要加1。这样做的好处是内部逻辑干净递归时depth 1的语义清晰不会出现根结点特殊处理的丑陋分支。比如下面这个对比定义方式根结点层次根的直接子结点适用场景0基深度01算法题、内部计算、图论1基层数12业务展示、组织架构、目录层级我个人的习惯是函数名叫getDepth就用0基叫getLevel就用1基命名和语义绑定谁看都不会误解。这一点看似吹毛求疵但在多人协作的项目里能省掉无数次沟通成本。2.2 指定结点是值还是引用差别巨大题目说指定结点但没说清楚这个指定是怎么指定的。有两种情况第一种是按值查找你给一个值让我在树里找到值等于它的结点然后返回层次。这种情况下如果树里存在重复值就会产生歧义——到底返回哪一个的层次是第一个找到的还是所有匹配中层次最小的这个必须在需求阶段问清楚。第二种是按引用查找你直接给我一个结点指针/引用让我算它在树里的层次。这种情况没有歧义但有个前提这个结点必须真的在这棵树里。如果传进来一个不属于这棵树的结点你得有处理策略——返回-1、抛异常、还是返回一个特殊标记。我在实际项目里更推荐按引用查找因为按值查找本质上把查找和算层次两件事耦合在了一起职责不单一。如果业务确实需要按值查那就先写一个通用的查找函数拿到结点引用再调用算层次的函数两步分开各自可测试。2.3 空树、单结点树、目标不存在这三种边界任何树相关的函数写完第一件事就是拿这三个用例去测空树根结点为null任何查找都应该返回不存在的标记。单结点树只有一个根如果目标就是根返回0或1如果不是返回不存在。目标不存在遍历完整棵树都没找到返回什么我一般用-1表示未找到因为层次不可能是负数语义清晰。很多人写递归时容易漏掉目标不存在这个分支导致函数返回了一个看起来像层次但其实是错误的值。比如下面这种典型错误写法def get_level_wrong(root, target): if root is None: return 0 if root target: return 1 left get_level_wrong(root.left, target) if left 0: return left 1 right get_level_wrong(root.right, target) if right 0: return right 1 return 0这段代码的问题在于当目标不在左子树时left返回0代码会继续去右子树找这没问题但如果目标真的不在整棵树里最后返回0而0又恰好是根结点的层次如果按0基算调用方根本无法区分没找到和找到了根。这就是语义冲突。正确做法是用-1表示未找到或者用一个额外的布尔标志。3. 递归解法三行代码背后的返回值语义设计3.1 自顶向下 vs 自底向上两种递归思路递归解这道题有两种完全不同的思路很多人只知其一。自顶向下的思路是从根开始往下走每往下一层就把当前深度加1传下去一旦遇到目标结点当前深度就是答案。这种思路的递归函数签名是dfs(node, current_depth, target)深度是带着走的参数。自底向上的思路是先假设子树里能找到目标让子树返回它相对自己的层次父结点拿到后再加1。这种思路的签名是dfs(node, target)深度是返回上来的结果。两种思路都能work但适用场景不同。自顶向下更适合找到就停的场景可以在找到目标后立即剪枝不用遍历完整棵树自底向上写起来更简洁但通常要遍历到目标所在子树才能确定结果。我一般推荐自顶向下因为它在平均情况下更快而且深度作为参数传递逻辑更直观。3.2 自顶向下递归的完整实现与逐行注释def get_level(root, target): 计算 target 结点在 root 为根的二叉树中的层次根为第0层 返回 -1 表示 target 不在树中 def dfs(node, depth): # 空结点说明这条路径走到底了也没找到 if node is None: return -1 # 命中目标当前 depth 就是答案 if node is target: return depth # 先在左子树找 left_result dfs(node.left, depth 1) if left_result ! -1: return left_result # 左子树没找到再去右子树 return dfs(node.right, depth 1) return dfs(root, 0)这段代码有几个细节值得说第一if node is target用的是is而不是这是按引用比较。如果你确实需要按值比较改成即可但要意识到重复值的问题。第二左子树找到后立即返回不再去右子树这是剪枝。如果目标在左子树右子树整棵都不用访问效率提升明显。第三depth 1在递归调用时传入而不是在返回时加这样每个结点的深度是自顶向下确定的不会因为回溯而出错。3.3 自底向上递归的写法与它的隐患def get_level_bottom_up(root, target): if root is None: return -1 if root is target: return 0 left get_level_bottom_up(root.left, target) if left ! -1: return left 1 right get_level_bottom_up(root.right, target) if right ! -1: return right 1 return -1这种写法看起来更短但有个隐患它无法剪枝。因为它是先递归到底再判断即使目标在左子树右子树的递归调用在某些写法下仍可能被触发取决于你判断的时机。上面这段代码其实做了优化左子树返回非-1就提前return了所以也能剪枝。但如果是那种先算left再算right最后合并的写法就会做无用功。我实测下来两种写法在随机二叉树上的性能差异不大但在目标结点偏向左侧的树上自顶向下略快。选哪个主要看个人习惯关键是返回值语义要统一。3.4 递归的栈深度问题一万个结点的链式树会怎样递归最大的风险是栈溢出。如果树退化成一条链每个结点只有左孩子树高等于结点数。在Python里默认递归深度限制是1000左右超过就抛RecursionError。也就是说一棵一万结点的链式树递归解法直接崩。import sys sys.setrecursionlimit(100000) # 可以调高但有真实栈溢出风险调高限制能解决一部分问题但治标不治本因为Python的递归帧占用真实内存调到十万级别可能直接把进程搞崩。所以如果你的树可能很深比如从数据库里读出来的层级数据深度不可控必须用迭代解法。这是工程经验和刷题经验的分水岭——刷题时树就几十个结点递归随便写工程里数据规模上来了递归就是定时炸弹。4. 迭代解法BFS逐层扫描才是工程里的稳妥选择4.1 用队列做层次遍历边遍历边计数迭代解法的核心是广度优先搜索BFS用队列逐层处理结点。每处理完一层层数加1一旦在某一层遇到目标直接返回当前层数。from collections import deque def get_level_bfs(root, target): if root is None: return -1 queue deque([root]) level 0 while queue: # 当前层的结点数 level_size len(queue) for _ in range(level_size): node queue.popleft() if node is target: return level if node.left: queue.append(node.left) if node.right: queue.append(node.right) level 1 return -1这段代码的关键在于level_size len(queue)这一行。它在每层开始时记录当前队列的长度这个长度就是这一层的结点数。内层for循环只处理这一层的结点处理完level加1进入下一层。如果不记录level_size直接while队列非空你就无法区分哪些结点属于同一层层数也就无从谈起。4.2 为什么BFS比DFS更适合求层次从算法角度DFS和BFS都能求层次时间复杂度都是O(n)。但从工程角度BFS有几个优势第一BFS天然按层推进层数是一个显式的变量不需要靠递归参数传递逻辑更直观不容易出错。第二BFS不会栈溢出它用的是堆上的队列队列大小最多是树的最大宽度对于大多数树来说远小于树高带来的递归深度。第三BFS可以提前终止一旦在当前层找到目标立即返回不需要访问后续层。如果目标在浅层BFS比DFS快得多。比如目标在根的直接子结点BFS最多访问3个结点就返回而DFS如果先走左子树且左子树很深可能要访问很多结点。当然BFS也有代价它需要O(w)的额外空间w是树的最大宽度。对于完全二叉树最后一层的宽度约等于n/2空间开销不小。但在实际工程里这个开销通常可以接受。4.3 迭代版DFS用显式栈模拟递归如果你既不想用递归怕栈溢出又想用DFS省空间可以用显式栈来模拟def get_level_dfs_iter(root, target): if root is None: return -1 # 栈里存 (结点, 深度) stack [(root, 0)] while stack: node, depth stack.pop() if node is target: return depth # 先压右再压左保证左子树先被处理 if node.right: stack.append((node.right, depth 1)) if node.left: stack.append((node.left, depth 1)) return -1这种写法的空间复杂度是O(h)h是树高比BFS的O(w)更省空间对于深而窄的树。但它的缺点是找到目标前可能要走很多冤枉路不像BFS那样按层推进。所以选BFS还是迭代DFS取决于你的树是宽而浅还是窄而深。4.4 三种解法的横向对比与选型建议解法时间复杂度空间复杂度栈溢出风险剪枝能力适用场景递归DFSO(n)O(h)有强树浅、代码简洁优先迭代DFSO(n)O(h)无强树深、空间敏感BFSO(n)O(w)无按层剪枝目标偏浅、层次直观我的选型建议很简单刷题或树浅用递归工程或树深用BFS。迭代DFS属于知道就好实际用得少因为它的代码比递归啰嗦空间优势又不如BFS直观。5. 工程实战里的变体多叉树、带父指针、海量数据5.1 多叉树场景把二叉改成children列表真实业务里的树很少是二叉的。组织架构、目录结构、分类体系都是多叉树。把上面的逻辑迁移到多叉树只需要把left/right换成children列表def get_level_nary(root, target): if root is None: return -1 queue deque([root]) level 0 while queue: level_size len(queue) for _ in range(level_size): node queue.popleft() if node is target: return level for child in node.children: queue.append(child) level 1 return -1改动极小核心逻辑完全一致。这也说明BFS解法的可迁移性比递归强——递归要改函数签名和返回值处理BFS只改一行入队逻辑。5.2 带父指针的树从目标往上走到根反而更快如果每个结点都存了指向父结点的指针那求层次就有了第三条路从目标结点出发沿着父指针一路往上走走到根为止走的步数就是层次。def get_level_with_parent(target): depth 0 node target while node.parent is not None: node node.parent depth 1 return depth这个解法的时间复杂度是O(h)只跟目标结点的深度有关跟整棵树的大小无关。如果目标在浅层它比遍历整棵树快得多。但它有两个前提一是结点必须带父指针二是必须能确认目标真的在这棵树里否则会走到null然后出错。带父指针的结构在工程里很常见比如DOM树、某些ORM的树形模型。如果你的数据结构支持优先用这个解法。5.3 海量结点下的性能考量一次遍历 vs 多次查询如果业务需要频繁查询不同结点的层次每次都从头遍历一遍树就很浪费。这时候有两个优化方向方向一预处理把每个结点的层次缓存起来。一次遍历用一个哈希表记录结点 - 层次的映射之后每次查询都是O(1)。def build_level_map(root): level_map {} if root is None: return level_map queue deque([(root, 0)]) while queue: node, depth queue.popleft() level_map[node] depth if node.left: queue.append((node.left, depth 1)) if node.right: queue.append((node.right, depth 1)) return level_map这个预处理是O(n)时间、O(n)空间之后每次查询O(1)。如果查询次数超过1次这个投入就回本了。方向二如果树是静态的不增删结点可以在建树时就把层次写进结点属性。这样连哈希表都省了直接读属性。代价是结点结构多一个字段内存占用略增。我个人的经验是查询次数少于3次直接遍历超过3次建缓存。这个阈值不是绝对的取决于树的规模和查询频率但大方向是这样。5.4 一个容易忽略的坑结点相等性判断前面代码里我一直用is做引用比较但很多语言或框架里结点的相等性判断是个坑。比如在某些语言里两个内容相同的结点对象可能不相等没有重写equals或者反过来两个不同位置的结点因为值相同被判等。如果你是按值查找一定要明确树里允不允许重复值如果允许返回哪一个我建议在函数文档里写清楚比如返回第一个匹配结点的层次遍历顺序为前序。如果业务需要返回所有匹配结点的层次那就把返回值改成列表收集所有匹配项。def get_all_levels(root, target_value): 返回所有值等于 target_value 的结点的层次列表 result [] def dfs(node, depth): if node is None: return if node.value target_value: result.append(depth) dfs(node.left, depth 1) dfs(node.right, depth 1) dfs(root, 0) return result这种返回所有匹配的写法在去重、统计类需求里很有用值得作为扩展掌握。6. 踩坑实录那些年我在求层次上翻过的车6.1 坑一把找不到和根结点混为一谈前面提过用0表示未找到而根结点层次也是0直接冲突。我第一次写这道题时就栽在这里测试用例里加了个目标不在树中的场景结果函数返回0测试断言期望-1直接挂掉。后来改成-1表示未找到问题解决。这个坑的本质是返回值语义不唯一。一个返回值承担了两种含义层次 存在性必然冲突。解决办法要么用-1这种哨兵值要么返回一个元组(found, level)要么抛异常。我推荐哨兵值简单直接。6.2 坑二递归时depth加错位置看这段错误代码def dfs(node, depth): if node is None: return -1 if node is target: return depth result dfs(node.left, depth) # 忘了加1 if result ! -1: return result return dfs(node.right, depth) # 忘了加1depth在递归调用时忘了加1导致所有结点的深度都是0。这种bug很隐蔽因为代码能跑不报错只是结果全错。排查方法是拿一棵三层的小树手动模拟打印每个结点的depth一眼就能看出问题。正确的做法是在向下传递时加1而不是在返回时加。因为返回时加1会导致每回溯一层加一次如果目标在深层回溯路径上的每一层都会加最终结果会偏大。6.3 坑三BFS里level_size算错时机BFS的层数计数关键在于level_size必须在每层开始时取而不是在循环中间取。看这个错误版本while queue: node queue.popleft() if node is target: return level if node.left: queue.append(node.left) if node.right: queue.append(node.right) level 1 # 错每处理一个结点就加一层这样写的话level加的是处理过的结点数不是层数。正确做法是用内层for循环处理完一整层再加。这个坑我在面试候选人时见过好几次属于BFS的经典易错点。6.4 坑四目标结点是null时的处理如果调用方传进来的target是null你的函数会怎样在按引用比较的写法里node is target在node为null时可能意外命中如果遍历到了叶子结点的空孩子。所以函数入口应该先判断target是否为null是的话直接返回-1。def get_level(root, target): if root is None or target is None: return -1 # ... 后续逻辑这个防御性判断花不了几行代码但能避免一类边界bug。工程代码里永远不要相信调用方传进来的参数是合法的该判空就判空。6.5 坑五树在遍历过程中被修改这个坑比较高级但在并发场景下真实存在。如果遍历树的同时另一个线程在增删结点你的遍历可能读到不一致的状态甚至陷入死循环。解决办法要么加锁要么用不可变树每次修改返回新树要么在遍历前做快照。这个超出了本题范围但值得知道——树不是线程安全的数据结构多线程访问要小心。7. 完整可运行的参考实现与测试用例7.1 定义树结点与建树辅助函数class TreeNode: def __init__(self, value, leftNone, rightNone): self.value value self.left left self.right right def build_sample_tree(): 1 / \ 2 3 / \ \ 4 5 6 / 7 n7 TreeNode(7) n6 TreeNode(6, leftn7) n5 TreeNode(5) n4 TreeNode(4) n3 TreeNode(3, rightn6) n2 TreeNode(2, leftn4, rightn5) n1 TreeNode(1, leftn2, rightn3) return n1, {n1: n1, n2: n2, n3: n3, n4: n4, n5: n5, n6: n6, n7: n7}7.2 用测试用例覆盖所有边界def run_tests(): root, nodes build_sample_tree() # 正常场景 assert get_level(root, nodes[n1]) 0 assert get_level(root, nodes[n2]) 1 assert get_level(root, nodes[n3]) 1 assert get_level(root, nodes[n4]) 2 assert get_level(root, nodes[n7]) 4 # 边界场景 assert get_level(None, nodes[n1]) -1 # 空树 assert get_level(root, None) -1 # 目标为null assert get_level(root, TreeNode(99)) -1 # 目标不在树中 # 单结点树 single TreeNode(1) assert get_level(single, single) 0 assert get_level(single, TreeNode(2)) -1 print(所有测试通过) run_tests()这套测试用例覆盖了正常路径、空树、单结点、目标不存在、目标为null五种情况。我建议你把这套用例作为模板以后写任何树相关的函数都照着改一遍能挡掉大部分低级bug。7.3 性能对比递归 vs BFS 在深树上的表现我做过一个简单的实测构造一棵一万结点的链式树每个结点只有左孩子目标是最深的那个结点。递归解法直接抛RecursionError需要调高递归限制才能跑调高后耗时约0.05秒但内存占用明显上升。BFS解法正常跑完耗时约0.08秒内存占用稳定。在链式树上BFS反而略慢因为它要维护一个队列而递归的调用开销在Python里其实也不小。但BFS胜在不会崩。在宽树上比如完全二叉树BFS的队列会膨胀到几千个结点内存占用上升但依然稳定。结论性能差异在可接受范围内稳定性才是选型的决定因素。工程代码优先选不会崩的方案。8. 从这道题延伸出去还能怎么玩8.1 求整棵树的最大深度与最小深度求指定结点层次是点查询求整棵树的最大深度是全局查询。最大深度用递归一行搞定def max_depth(root): if root is None: return 0 return 1 max(max_depth(root.left), max_depth(root.right))最小深度稍微麻烦点因为要处理只有一个孩子的情况——不能简单取min否则会走到空孩子那边返回0。正确写法是分情况讨论def min_depth(root): if root is None: return 0 if root.left is None: return 1 min_depth(root.right) if root.right is None: return 1 min_depth(root.left) return 1 min(min_depth(root.left), min_depth(root.right))这两个函数和求指定结点层次是同一类问题的不同变体掌握一个另外两个触类旁通。8.2 求两个结点的最近公共祖先这是求层次的进阶版。知道两个结点的层次后可以先把深的那个往上提到和浅的一样深然后两个一起往上走直到相遇。这个算法叫双指针爬树前提是结点带父指针。如果不带父指针就得用递归后序遍历判断两个目标是否分别在左右子树。def lowest_common_ancestor(root, p, q): if root is None or root is p or root is 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这道题在面试里出现频率极高而它的基础就是理解结点在树中的位置关系跟求层次是同一个知识体系。8.3 树形数据的路径还原知道一个结点的层次后如果还想知道从根到它的完整路径可以在遍历时维护一个路径栈。每进入一个结点就压栈离开就弹栈找到目标时栈里的内容就是路径。def find_path(root, target): path [] def dfs(node): if node is None: return False path.append(node) if node is target: return True if dfs(node.left) or dfs(node.right): return True path.pop() return False if dfs(root): return path return []这个技巧在文件目录、面包屑导航、组织架构路径展示里非常实用。层次告诉你有多深路径告诉你怎么走两者结合树形数据的定位问题就完整了。8.4 层次信息在可视化里的应用如果你做过树形图的可视化就知道每个结点的坐标计算离不开层次。通常横坐标由中序遍历顺序决定纵坐标由层次决定——层次越深y坐标越大。所以求层次这个操作在渲染引擎里是高频调用这也是为什么前面强调查询次数多就建缓存。一个典型的渲染流程是先遍历一次树算出每个结点的层次和水平位置存进布局对象然后统一绘制。这样避免了在绘制过程中反复计算性能提升明显。9. 我个人的几条实操心得写了这么多最后分享几条我在实际项目里总结的经验都是踩过坑才明白的。第一条函数入口先判空别嫌啰嗦。空树、空目标、目标不在树里这三个判断加起来不到五行代码但能挡掉80%的线上bug。我见过太多理论上不会为空的假设最后都在生产环境被打脸。第二条返回值语义要唯一。一个返回值只表达一个意思。层次就是层次找不到就用-1或抛异常别让0既表示根又表示找不到。这个原则适用于所有函数设计不只是树。第三条树深超过一千果断放弃递归。不要心存侥幸去调递归限制那只是把崩溃推迟到更难排查的地方。BFS的代码多写几行换来的是稳定。第四条频繁查询就预处理。如果同一个树的层次要被查很多次一次遍历建哈希表后面全是O(1)。这个优化的投入产出比极高几乎没有任何理由不做。第五条测试用例要覆盖边界。空树、单结点、目标不存在、目标为null、链式树、完全二叉树这六种情况跑一遍基本就稳了。我现在的习惯是写完树相关函数先把这六个用例过一遍再提交。这套东西看起来是围绕一道小题展开的但里面的思路——边界处理、返回值设计、递归与迭代的取舍、预处理换查询效率——是通用的。下次你遇到求某个结点在树里的位置这类需求直接把这套框架套上去就行。