1. 從一個看似簡單的二叉樹問題說起計算二叉樹中指定結點所在的層次——這個標題看起來像是數據結構課程里的一道基礎練習題但真正動手寫過的人都知道它背后牽扯的東西遠比想象中多。層次的定義本身就有歧義根結點算第0層還是第1層這個問題在不同的教材、不同的面試官嘴里答案可能完全不一樣。更別提實際工程中二叉樹可能不是標準的鏈式結構可能是數組存儲的完全二叉樹可能是帶父指針的三叉鏈表甚至可能是序列化后的字符串形式。我在過去幾年里至少在三類場景中反復遇到過這個問題一是面試輔導時學員被追問如果結點不存在怎么辦二是做代碼審查時發(fā)現同事用遞歸返回值判斷層次結果遇到空樹直接棧溢出三是幫一個做文件系統目錄樹分析的朋友優(yōu)化查詢邏輯他的樹有幾十萬個結點每次查層次都要重新遍歷一遍性能慘不忍睹。這篇文章就是把這些年踩過的坑、總結出來的套路以及不同場景下該怎么選方案一次性講清楚。不管你是正在準備數據結構考試的學生還是工作中需要處理樹形結構的開發(fā)者或者是想搞清楚遞歸和迭代到底該怎么選的初學者下面這些內容應該都能直接拿來用。我會從最基礎的遞歸思路開始逐步展開到迭代方案、帶父指針的優(yōu)化、數組存儲的特殊處理最后給出完整的可運行代碼和性能對比。2. 核心思路拆解與方案選型2.1 層次定義的統一約定在動手寫任何代碼之前必須先和所有相關方對齊一個約定根結點的層次是多少。我見過太多因為這個問題沒對齊導致返工的案例。常見的約定有兩種根結點為第1層這是國內大多數數據結構教材比如嚴蔚敏版采用的約定符合人類直覺樹的總層數就是樹的高度。根結點為第0層部分算法競賽和國外教材采用這種約定在計算路徑長度、深度等指標時數學上更簡潔。我的建議是在函數命名和注釋中顯式寫明約定。比如函數名叫getLevelFromOne或者getDepthFromZero這樣調用方一眼就能看懂不需要去翻文檔。如果團隊有統一規(guī)范那就嚴格遵循如果沒有就在代碼里加一行注釋說明成本極低但收益巨大。注意面試時如果面試官沒有明確說明一定要主動問一句根結點算第幾層這不僅是確認需求也體現了你的嚴謹性。2.2 遞歸方案的核心邏輯遞歸是解決樹形結構問題最自然的思路。要計算某個結點所在的層次可以轉化為從根結點出發(fā)沿著某條路徑往下找每走一層計數器加一找到目標結點時返回當前計數。用遞歸的語言描述就是如果當前結點就是目標結點返回當前層次否則分別在左子樹和右子樹中查找如果左子樹找到了就返回左子樹的結果否則返回右子樹的結果都沒找到就返回一個表示未找到的特殊值。這里有一個關鍵細節(jié)遞歸函數的返回值設計。很多初學者會寫成返回布爾值表示是否找到然后通過全局變量記錄層次。這種寫法雖然能跑通但破壞了函數的純粹性在多線程環(huán)境下會出問題。更好的做法是讓遞歸函數直接返回層次值用一個特殊值比如-1表示未找到。2.3 迭代方案為什么也值得掌握遞歸寫起來簡潔但有兩個硬傷一是遞歸深度受調用棧限制如果樹退化成鏈表比如按順序插入的有序二叉樹幾萬個結點就可能導致棧溢出二是遞歸的函數調用開銷在性能敏感場景下不可忽略。迭代方案通常借助隊列做層次遍歷BFS在遍歷過程中記錄每個結點的層次。當遇到目標結點時直接返回當前層次。這種寫法的時間復雜度和遞歸一樣都是O(n)但空間復雜度在最壞情況下也是O(n)隊列中最多同時存在一層的結點而遞歸的空間復雜度是O(h)h為樹高。兩者各有優(yōu)劣具體選哪個要看樹的形態(tài)和運行環(huán)境。2.4 帶父指針的三叉鏈表優(yōu)化如果樹結構中每個結點額外存儲一個指向父結點的指針那么問題就變得非常簡單從目標結點出發(fā)沿著父指針一路向上走到根結點走過的邊數加一就是層次。這種方案的時間復雜度是O(h)不需要遍歷整棵樹在只需要查詢少量結點層次時優(yōu)勢明顯。代價是每個結點多了一個指針的存儲開銷以及在插入、刪除結點時需要維護父指針的正確性。這是一種典型的空間換時間策略適合查詢頻繁但修改較少的場景。2.5 數組存儲的完全二叉樹特殊處理對于用數組存儲的完全二叉樹堆就是典型例子結點下標和層次之間有直接的數學關系。如果根結點存在下標0處那么下標為i的結點所在層次是floor(log2(i1)) 1根為第1層或者floor(log2(i1))根為第0層。這個公式的推導很簡單完全二叉樹中第k層的結點下標范圍是[2^(k-1)-1, 2^k-2]根為第1層根下標為0。對下標i取以2為底的對數再向下取整就能反推出層次。這種方案的時間復雜度是O(1)是所有方案中最快的但只適用于數組存儲的完全二叉樹。3. 核心細節(jié)解析與實操要點3.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 1但left本身已經是左子樹中目標結點相對于左子樹根的層次加上1之后確實是從當前結點看的層次。邏輯上似乎沒問題但仔細想如果目標結點就是左子樹的根left返回1加1變成2而從當前結點看它確實在第2層沒問題。真正的問題出在空樹的處理和未找到的表示上。如果樹為空返回0調用方無法區(qū)分樹為空和目標結點在第0層如果約定根為第0層的話。所以更穩(wěn)妥的做法是用-1表示未找到并且明確約定根結點的層次。3.2 迭代BFS的層次記錄技巧用隊列做層次遍歷時如何知道當前處理的是第幾層常見的有兩種做法第一種是雙隊列法用兩個隊列一個存當前層的結點一個存下一層的結點。當前層處理完后交換兩個隊列層次加一。這種寫法邏輯清晰但需要額外的隊列空間。第二種是單隊列加計數法每次處理前先記錄當前隊列的長度size然后連續(xù)處理size個結點這size個結點就是同一層的。處理完這size個后層次加一。這種寫法只需要一個隊列空間利用率更高是我更推薦的方式。from collections import deque def get_level_bfs(root, target, root_level1): if root is None: return -1 queue deque([root]) level root_level while queue: size len(queue) for _ in range(size): node queue.popleft() if node target: return level if node.left: queue.append(node.left) if node.right: queue.append(node.right) level 1 return -1這段代碼中size的記錄是關鍵。如果不記錄size直接一邊出隊一邊入隊就無法區(qū)分哪些結點屬于同一層。3.3 父指針方案的邊界處理帶父指針的方案看起來最簡單但有幾個邊界情況容易出錯目標結點就是根結點此時父指針為None循環(huán)一次都不執(zhí)行直接返回根結點的層次。目標結點不在樹中如果調用方傳入了一個不屬于這棵樹的結點沿著父指針走可能會走到別的樹上去或者陷入死循環(huán)如果父指針有環(huán)。所以這種方案通常要求調用方保證結點屬于該樹。根結點的層次約定如果根為第1層那么從目標結點走到根結點經過的邊數加1就是層次如果根為第0層邊數就是層次。def get_level_with_parent(node, root_level1): level root_level current node while current.parent is not None: level 1 current current.parent return level這段代碼假設了node一定在樹中且根結點的parent為None。實際使用時可以在走到根結點后檢查一下根結點是否是預期的根以確認結點確實屬于這棵樹。3.4 數組存儲的公式推導與驗證對于根結點下標為0的完全二叉樹下標i的結點層次計算公式推導如下第1層只有根結點下標0滿足floor(log2(01)) 1 0 1 1。 第2層有下標1、2兩個結點floor(log2(11)) 1 1 1 2floor(log2(21)) 1 1 1 2。 第3層有下標3、4、5、6四個結點floor(log2(31)) 1 2 1 3以此類推。驗證一下邊界下標7是第4層的第一個結點floor(log2(71)) 1 3 1 4正確。下標14是第4層的最后一個結點floor(log2(141)) 1 3 1 4正確。下標15是第5層的第一個結點floor(log2(151)) 1 4 1 5正確。import math def get_level_array(index, root_level1): if index 0: return -1 level_from_zero int(math.log2(index 1)) if root_level 1: return level_from_zero 1 return level_from_zero注意用浮點數計算log2時對于非常大的下標可能會有精度問題。更穩(wěn)妥的做法是用位運算index 1的二進制表示中最高位1的位置就是層次從0開始計數。Python中可以用(index 1).bit_length() - 1來獲取。4. 完整實操過程與核心環(huán)節(jié)實現4.1 定義二叉樹結點結構為了演示所有方案我先定義一個通用的二叉樹結點類包含數據域、左右子指針和可選的父指針class TreeNode: def __init__(self, val0, leftNone, rightNone, parentNone): self.val val self.left left self.right right self.parent parent如果不需要父指針方案parent字段可以省略。如果需要父指針在構建樹的時候要記得同步維護def build_tree_with_parent(values): if not values: return None nodes [TreeNode(v) if v is not None else None for v in values] for i, node in enumerate(nodes): if node is None: continue left_idx 2 * i 1 right_idx 2 * i 2 if left_idx len(nodes) and nodes[left_idx] is not None: node.left nodes[left_idx] nodes[left_idx].parent node if right_idx len(nodes) and nodes[right_idx] is not None: node.right nodes[right_idx] nodes[right_idx].parent node return nodes[0] if nodes else None這段代碼按層序數組構建二叉樹同時維護父指針。注意values中的None表示空結點但空結點的子結點下標仍然按照完全二叉樹的規(guī)則計算這是層序數組構建的標準做法。4.2 遞歸方案的完整實現def get_level_recursive(root, target, current_level1): 遞歸計算目標結點所在層次。 root: 當前子樹的根 target: 目標結點 current_level: 當前子樹根的層次 返回目標結點的層次未找到返回-1。 if root is None: return -1 if root is target: return current_level left_result get_level_recursive(root.left, target, current_level 1) if left_result ! -1: return left_result return get_level_recursive(root.right, target, current_level 1)這個實現把當前層次作為參數傳遞避免了返回值加一的混亂。邏輯非常清晰當前結點是目標就返回當前層次否則先查左子樹左子樹找到就返回否則查右子樹。都沒找到返回-1。調用方式get_level_recursive(root, target_node, 1)根結點為第1層。4.3 迭代BFS方案的完整實現from collections import deque def get_level_bfs(root, target, root_level1): 迭代BFS計算目標結點所在層次。 返回目標結點的層次未找到返回-1。 if root is None: return -1 queue deque([root]) level root_level while queue: level_size len(queue) for _ in range(level_size): node queue.popleft() if node is target: return level if node.left is not None: queue.append(node.left) if node.right is not None: queue.append(node.right) level 1 return -1這里用is而不是來比較結點是因為我們比較的是對象身份而不是值。如果樹中有重復值用可能會匹配到錯誤的結點。當然如果業(yè)務邏輯就是按值查找那用也合理但要在文檔中寫清楚。4.4 父指針方案的完整實現def get_level_with_parent(node, root, root_level1): 利用父指針計算結點層次。 node: 目標結點 root: 樹的根結點用于驗證結點確實屬于這棵樹 返回目標結點的層次如果結點不屬于這棵樹返回-1。 if node is None: return -1 level root_level current node while current.parent is not None: level 1 current current.parent if current is not root: return -1 return level最后一步current is not root的檢查很重要它防止了傳入一個不屬于該樹的結點時返回錯誤的層次。走到最上面后如果根結點不是預期的根說明這個結點在另一棵樹里。4.5 數組存儲方案的完整實現def get_level_array(index, root_level1): 計算完全二叉樹中下標為index的結點層次。 假設根結點下標為0。 if index 0: return -1 level_from_zero (index 1).bit_length() - 1 if root_level 1: return level_from_zero 1 return level_from_zero用bit_length()代替log2避免了浮點數精度問題而且位運算速度更快。(index 1).bit_length()返回的是二進制表示所需的位數減一就是最高位1的位置也就是從0開始計數的層次。4.6 性能對比與選型建議方案時間復雜度空間復雜度適用場景注意事項遞歸O(n)O(h)樹高較小代碼簡潔優(yōu)先樹退化成鏈表時可能棧溢出迭代BFSO(n)O(n)樹高較大避免遞歸需要額外隊列空間父指針O(h)O(1)查詢頻繁修改較少需要額外存儲父指針數組公式O(1)O(1)完全二叉樹數組存儲只適用于完全二叉樹選型建議如果只是偶爾查詢一次遞歸最省事如果樹可能很深用迭代BFS如果需要頻繁查詢不同結點的層次考慮加父指針如果是堆這類完全二叉樹直接用公式。5. 常見問題與排查技巧實錄5.1 遞歸棧溢出怎么排查和解決棧溢出通常表現為RecursionError: maximum recursion depth exceeded。排查方法很簡單打印樹的高度如果高度接近或超過Python默認的遞歸限制通常是1000那基本就是這個問題。解決方案有三種一是改用迭代BFS二是手動增加遞歸限制sys.setrecursionlimit(100000)但這只是治標樹足夠大還是會崩三是用尾遞歸優(yōu)化但Python不支持尾遞歸優(yōu)化所以這條對Python無效。我個人的經驗是只要樹的高度可能超過500就直接用迭代不要猶豫。遞歸寫起來是爽但線上環(huán)境崩一次的成本遠高于多寫幾行迭代代碼。5.2 目標結點不存在時返回什么這是一個接口設計問題。返回-1是常見做法但如果層次本身可能為-1比如根為第0層空樹返回-1就會有歧義。更穩(wěn)妥的做法是返回None或者拋異常。我的建議是如果結點不存在是正常業(yè)務邏輯的一部分返回None如果是異常情況拋異常。比如在文件系統目錄樹中查找某個文件文件不存在是正常的返回None但如果傳入的根結點是None那是調用方的bug應該拋異常。5.3 樹中有重復值時怎么處理如果樹中允許重復值按值查找就會有問題。比如要找值為5的結點樹中有三個值為5的結點返回哪個的層次解決方案有兩種一是按結點引用查找調用方直接傳入目標結點的引用這樣最準確二是按值查找時明確約定返回第一個找到的比如層序遍歷中最早出現的并在文檔中寫清楚。我在實際項目中更傾向于第一種因為按值查找在重復值場景下語義不明確容易埋坑。5.4 父指針維護遺漏導致層次計算錯誤帶父指針的方案中最常見的bug是插入或刪除結點時忘記更新父指針。比如插入一個新結點時只設置了父結點的子指針沒有設置新結點的父指針導致新結點的parent為None計算層次時直接返回根結點的層次。排查方法寫一個校驗函數遍歷整棵樹檢查每個非根結點的parent是否指向正確的父結點。這個校驗函數在單元測試中非常有用。def validate_parent_pointers(root): 校驗樹中所有結點的父指針是否正確。 if root is None: return True if root.left is not None: if root.left.parent is not root: return False if not validate_parent_pointers(root.left): return False if root.right is not None: if root.right.parent is not root: return False if not validate_parent_pointers(root.right): return False return True5.5 數組公式在非完全二叉樹上的誤用數組公式只適用于完全二叉樹。如果樹不是完全二叉樹但用數組存儲時中間有空缺公式計算出的層次就是錯的。比如一棵只有左子樹的樹根下標0左子結點下標1左子結點的左子結點下標3但下標2是空的。此時下標3的結點實際在第3層公式計算(31).bit_length() - 1 2加一得3看起來對。但如果下標2的位置實際上有結點只是邏輯上不屬于這棵樹公式就會把它也算進去。所以使用數組公式前必須確認樹是完全二叉樹且數組中沒有邏輯上不屬于該樹的占位元素。5.6 常見問題速查表問題現象可能原因排查方法解決方案遞歸棧溢出樹太高打印樹高改用迭代BFS返回層次總是根層次父指針未維護校驗父指針插入刪除時同步更新找不到目標結點比較方式錯誤檢查用is還是按引用查找用is數組公式結果錯誤樹不是完全二叉樹檢查樹形態(tài)改用遞歸或迭代層次差一根層次約定不一致檢查調用參數統一約定并寫注釋實操心得在寫單元測試時一定要覆蓋空樹、單結點樹、目標結點是根、目標結點是葉子、目標結點不存在這五種情況。這五種情況覆蓋了絕大多數邊界bug。6. 不同場景下的方案選擇與擴展思路6.1 面試場景下的答題策略面試時遇到這個問題面試官通常不只是想看你寫出代碼更想看你如何分析問題。我的建議是分三步走第一步確認需求。問清楚根結點算第幾層結點不存在時返回什么樹的結構是標準的鏈式結構還是其他形式。第二步先說思路再寫代碼?？梢韵日f遞歸方案因為最直觀然后提一句迭代方案可以避免棧溢出如果面試官追問優(yōu)化再提父指針和數組公式。第三步寫完代碼后主動分析時間空間復雜度并指出邊界情況。比如這段代碼在空樹時返回-1目標結點是根時返回1這些我都考慮到了。6.2 工程場景下的性能優(yōu)化在實際工程中如果樹的結構經常變動但查詢層次的需求很頻繁可以考慮在結點中緩存層次信息。每次插入刪除時更新受影響結點的層次緩存查詢時直接讀取。這種方案的時間復雜度是O(1)但維護成本較高適合讀寫比非常懸殊的場景。另一種優(yōu)化思路是路徑壓縮第一次查詢某個結點的層次時把路徑上所有結點的層次都計算出來并緩存。后續(xù)查詢這些結點時直接返回緩存值。這種方案在多次查詢同一棵樹的場景下效果很好。6.3 擴展到N叉樹和森林N叉樹的層次計算和二叉樹思路完全一樣只是遞歸時要遍歷所有子結點而不是左右兩個。迭代BFS時把左右子結點換成子結點列表即可。森林的層次計算稍微復雜一點森林中每棵樹的根結點層次都是1或者0計算某個結點的層次時先找到它屬于哪棵樹然后在那棵樹里計算。如果森林是用左子右兄弟表示法存儲的那就要注意區(qū)分子結點和兄弟結點不要混淆。6.4 擴展到帶權樹的最短路徑層次如果樹的邊上帶權值層次的定義就變得模糊了是按邊數算還是按權值和算如果是按權值和算那問題就變成了從根結點到目標結點的路徑長度可以用DFS或BFS配合累加權值來解決。這種場景在路由算法、網絡拓撲分析中比較常見。我在一個網絡拓撲分析的項目中就遇到過類似需求計算某個網絡設備在拓撲樹中的邏輯層次但邊權表示的是延遲所以層次實際上是累計延遲。這種場景下遞歸和迭代方案都需要額外傳遞一個累加值參數。6.5 一個容易忽略的細節(jié)結點比較方式最后再強調一個細節(jié)在Python中比較兩個對象時調用的是__eq__方法is比較的是對象身份。如果TreeNode類沒有重寫__eq__那和is效果一樣。但如果重寫了__eq__比如按值比較那用查找可能會匹配到值相同但實際不同的結點。我的建議是在樹結構相關的代碼中一律用is比較結點除非你明確知道自己在做什么。這樣可以避免很多隱蔽的bug。如果確實需要按值查找單獨寫一個按值查找的函數并在函數名和文檔中明確說明。def find_node_by_value(root, value): 按值查找結點返回第一個匹配的結點未找到返回None。 if root is None: return None if root.val value: return root left_result find_node_by_value(root.left, value) if left_result is not None: return left_result return find_node_by_value(root.right, value)這個函數和層次計算函數配合使用就可以實現按值查找并返回層次的功能而且語義清晰不容易出錯。6.6 完整測試用例最后給出一組完整的測試用例覆蓋各種邊界情況def test_get_level(): # 構建測試樹 # 1 # / \ # 2 3 # / \ \ # 4 5 6 root TreeNode(1) root.left TreeNode(2, parentroot) root.right TreeNode(3, parentroot) root.left.left TreeNode(4, parentroot.left) root.left.right TreeNode(5, parentroot.left) root.right.right TreeNode(6, parentroot.right) # 根結點為第1層 assert get_level_recursive(root, root, 1) 1 assert get_level_recursive(root, root.left, 1) 2 assert get_level_recursive(root, root.left.left, 1) 3 assert get_level_recursive(root, root.right.right, 1) 3 # 目標結點不存在 orphan TreeNode(99) assert get_level_recursive(root, orphan, 1) -1 # 空樹 assert get_level_recursive(None, root, 1) -1 # 迭代方案 assert get_level_bfs(root, root, 1) 1 assert get_level_bfs(root, root.left.left, 1) 3 assert get_level_bfs(root, orphan, 1) -1 # 父指針方案 assert get_level_with_parent(root, root, 1) 1 assert get_level_with_parent(root.left.left, root, 1) 3 assert get_level_with_parent(orphan, root, 1) -1 # 數組方案 assert get_level_array(0, 1) 1 assert get_level_array(1, 1) 2 assert get_level_array(2, 1) 2 assert get_level_array(3, 1) 3 assert get_level_array(6, 1) 3 assert get_level_array(7, 1) 4 print(所有測試通過) test_get_level()這組測試覆蓋了根結點、中間結點、葉子結點、不存在的結點、空樹、以及數組方案的各種邊界。跑通這組測試基本可以保證代碼的正確性。我個人在實際操作中的體會是二叉樹層次計算這個問題看起來簡單但真正寫好、寫對、寫到能上生產環(huán)境需要考慮的細節(jié)非常多。最重要的不是記住某一種寫法而是理解每種方案背后的取舍邏輯這樣遇到新場景時才能快速選出合適的方案。另外不管用哪種方案單元測試一定要覆蓋邊界情況我見過太多因為空樹或結點不存在導致線上報錯的案例了。