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