1. 題目理解與BFS思路分析LeetCode 1161 這道題標題寫得很直白最大層內(nèi)元素和。第一眼看到 BFS 這個標簽我基本就確定了解題路線——二叉樹的層序遍歷用隊列逐層掃過去每層累加求和記錄最大值出現(xiàn)的層號。這道題在 LeetCode 上屬于中等偏簡單的那一檔非常適合用來鞏固 BFS 的分層處理技巧尤其是剛學完二叉樹遍歷、想從 DFS 過渡到 BFS 的讀者拿它練手再合適不過。1.1 題面在問什么層內(nèi)元素和題目給一棵二叉樹要求返回“元素和最大”的那一層的層號。注意幾個關鍵詞層號從 1 開始根節(jié)點就是第 1 層。元素和是整層所有節(jié)點值的代數(shù)和節(jié)點值有正有負。如果存在多個層的元素和并列最大返回層號最小的那一層。舉個例子root [1, 7, 0, 7, -8, null, null]這棵樹結(jié)構(gòu)是1 / \ 7 0 / \ 7 -8第 1 層只有根節(jié)點和是1第 2 層有7和0和是7第 3 層有7和-8和是-1。三層里面最大的是第 2 層所以答案返回2。這個例子有個容易踩的細節(jié)如果把第 3 層的-8漏掉就會誤以為第 3 層只有7然后把最大層算錯。題目里的節(jié)點值允許為負意味著求和結(jié)果不能單純按照“哪層節(jié)點多哪層就大”來猜必須老老實實逐層加完再比。1.2 為什么第一反應是 BFS看到“層內(nèi)元素和”最直接的想法就是把每一層的節(jié)點單獨拎出來算一遍。二叉樹里能做到“一層一層拎出來”的遍歷方式就是層序遍歷也就是 BFS。BFS 的實現(xiàn)思路很自然用一個隊列先把根節(jié)點放進去然后不斷從隊頭彈出節(jié)點同時把它的左右孩子放到隊尾。這樣彈出順序天然是按照層來推進的而且彈出的節(jié)點會自動按層分組。這里我習慣用一個生活類比BFS 就像坐電梯逐層掃樓每層從左到右把住戶全訪問一遍再上下一層DFS 則像走樓梯一條道走到黑走到?jīng)]路了再退回岔路口。題目要按層統(tǒng)計電梯邏輯顯然更貼合。BFS 分層還有一個隱藏優(yōu)勢每層之間的邊界很清晰只要在每次循環(huán)開始時記錄一下當前隊列長度這個長度就是當前層節(jié)點的數(shù)量處理完這個數(shù)量就說明這一層結(jié)束了。這個“記錄 size 再消費”的技巧是絕大多數(shù) BFS 分層題的核心后面的實現(xiàn)里我會重點講。1.3 DFS 也能做但不推薦當然DFS 并不是不能做。用遞歸或者顯式棧去做深度優(yōu)先遍歷同時維護每個節(jié)點所在的深度每到一個節(jié)點就把值累加到對應深度的桶里最后再從桶里找出和最大的那個深度。思路沒問題代碼也能過。但不推薦的原因有兩個。第一是邏輯繞。DFS 天然是往深處走的為了知道當前在第幾層遞歸參數(shù)里必須多帶一個depth或者用棧模擬時維護節(jié)點和深度的元組。對于一棵層數(shù)很深的樹遞歸還有爆棧風險。而 BFS 的層號天生就跟著循環(huán)走不需要額外維護。第二是空間消耗。DFS 需要維護一個長度等于樹高的數(shù)組或哈希表來存每一層的和。樹高可能達到n退化成鏈表這樣空間就是 O(n)BFS 雖然隊列也可能達到 O(n)但大多數(shù)樹結(jié)構(gòu)下 BFS 的隊列峰值是樹的寬度兩者在理論上界相同實際卻更可控。既然 BFS 更符合直覺、代碼更短自然選它。2. 核心細節(jié)BFS 層序遍歷的完整拆解這道題的解題模板其實就是 BFS 分層遍歷的通用寫法。把每一行代碼拆開看你會發(fā)現(xiàn)每個細節(jié)都有它存在的理由少了哪個都可能出 bug。2.1 隊列初始化與判空BFS 需要借助隊列。Java 里我一般用LinkedList來實現(xiàn)Queue接口原因很簡單LinkedList允許存null而ArrayDeque不允許。雖然二叉樹遍歷時我們通常不會往隊列里放null但萬一想用null做層分隔符LinkedList會更靈活。入隊和出隊方法我強烈建議用offer()和poll()而不是add()和remove()。原因在于add()在隊列滿時會拋異常remove()在隊列空時會拋異常而offer()和poll()分別返回false和null雖然在我們手寫的 BFS 里幾乎不會觸達這些邊界但用返回狀態(tài)的方法始終更安全。判空這一步容易被忽略。題目雖然保證root非空但寫成if (root null) return 0;是零成本防御。為什么返回0而不是1因為空樹壓根沒有層返回任意非 0 層號都是錯的按“不存在”處理返回 0 最合理。2.2 size快照鎖定當前層的邊界這是 BFS 分層三要素里的第一要素進入每層處理前先把當前隊列長度拍個快照。int size queue.size();千萬別寫成for (int i 0; i queue.size(); i)因為循環(huán)體里會不斷把子節(jié)點入隊queue.size()會隨著迭代變化原本只想處理本層節(jié)點結(jié)果可能把下一層的新節(jié)點也一并消費掉層邊界直接崩掉。正確做法是在進入循環(huán)之前把當前層的節(jié)點數(shù)存到size變量里然后只從這個數(shù)量范圍內(nèi)彈節(jié)點。這個快照就是“當前層的節(jié)點清單”是 BFS 分層的錨點。這里順便解釋一個初學者常困惑的點為什么每層處理的次數(shù)是size而不是一直while (!queue.isEmpty())因為隊列里既有當前層節(jié)點也有已經(jīng)入隊的下一層節(jié)點。要區(qū)分“現(xiàn)在正在處理哪一層”靠的就是這個快照。一直while循環(huán)會把所有層混在一次處理里求和當然就對不上號了。2.3 sum清零與層計數(shù)器每層開始前求和變量必須歸零。我第一次寫這道題的時候把sum定義在了while外層結(jié)果第一層的和累加了第二層第二層又累加了第三層最后答案完全錯亂。這是一個看起來不起眼、實際非常致命的細節(jié)。正確邏輯是每進入一層sum 0;然后在該層內(nèi)把所有節(jié)點值加進去處理完這一層后立刻拿sum和當前最大值比較比較完再進入下一層。注意sum清零的時機必須是在進入該層時而不是比較之后——如果你在比較完才清零下一層開始前已經(jīng)帶著上一層的數(shù)據(jù)了。層計數(shù)器level的遞增位置也有講究。它應該在外層while循環(huán)開始后、內(nèi)層for循環(huán)之前l(fā)evel表示“我馬上要處理第 level 層的節(jié)點”。這個順序保證了第一個處理的層號是 1和題目要求一致。2.4 最大值的初始化與更新策略這里藏著一個經(jīng)典的坑最大值初始值不能寫0。因為節(jié)點值可能全為負數(shù)。比如樹只有[-1, -2, -3]每層的和都是負數(shù)如果把maxSum初始化為0任何一層都不可能大于0最終答案永遠是初始的層號而不是真正的最大層。正確初始化是Integer.MIN_VALUE在 C 里是INT_MINPython 里是float(-inf)。這樣第一層比較時無論值多小都會被正確接收。更新策略同樣有講究題目要求“最大和相同返回最靠前的層”所以比較條件必須用不能用。if (sum maxSum) { maxSum sum; ans level; }如果用遇到并列最大值時會不斷把ans更新成更靠后的層號最終返回的就是最大層的最深處和題意正好相反。這個細節(jié)題目里通常不會特別標紅但測試用例一定會覆蓋丟分丟得冤。3. 多語言實現(xiàn)一份思路三種寫法同一個 BFS 思路在不同語言里寫法略有差異但骨架完全一致。我把三種常用語言的版本都貼出來并標注每一步的作用方便你對照著理解也方便平時用自己熟悉的語言刷題。3.1 Java 版本class Solution { public int maxLevelSum(TreeNode root) { if (root null) return 0; QueueTreeNode queue new LinkedList(); queue.offer(root); int maxSum Integer.MIN_VALUE; int level 0; int ans 1; while (!queue.isEmpty()) { int size queue.size(); int sum 0; level; for (int i 0; i size; i) { TreeNode node queue.poll(); sum node.val; if (node.left ! null) queue.offer(node.left); if (node.right ! null) queue.offer(node.right); } if (sum maxSum) { maxSum sum; ans level; } } return ans; } }這個版本里Queue接口 LinkedList的組合是最常見的 BFS 寫法。offer/poll代替add/remove前面已經(jīng)解釋過原因。TreeNode是 LeetCode 內(nèi)置的二叉樹節(jié)點類包含val、left、right三個字段直接用即可。有個小細節(jié)ans初始化為1。因為題目至少有一層即使第一層的和是最小的比較后也會被正確更新為第一層。假如初始化成0當樹只有一層時最后返回0就會出錯。所以ans初始化為 1 是穩(wěn)妥的配合maxSum MIN_VALUE第一層一定觸發(fā)更新。3.2 C 版本class Solution { public: int maxLevelSum(TreeNode* root) { if (!root) return 0; queueTreeNode* q; q.push(root); int maxSum INT_MIN; int level 0; int ans 1; while (!q.empty()) { int size q.size(); int sum 0; level; for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); sum node-val; if (node-left) q.push(node-left); if (node-right) q.push(node-right); } if (sum maxSum) { maxSum sum; ans level; } } return ans; } };C 里注意q.front()只取隊頭元素但不會彈出需要單獨q.pop()移除。這個兩步操作經(jīng)常有初學者漏掉pop導致死循環(huán)。另外if (node-left)這種寫法可以直接判空比 Java 的! null更簡潔原理是空指針隱式轉(zhuǎn)換成false。INT_MIN來自climits頭文件LeetCode 環(huán)境已經(jīng)默認包含所以不用手動引入。如果用long long來存sum那maxSum類型也要同步改成long long注意類型一致性。3.3 Python 版本from collections import deque class Solution: def maxLevelSum(self, root: Optional[TreeNode]) - int: if not root: return 0 q deque([root]) max_sum float(-inf) level 0 ans 1 while q: size len(q) total 0 level 1 for _ in range(size): node q.popleft() total node.val if node.left: q.append(node.left) if node.right: q.append(node.right) if total max_sum: max_sum total ans level return ansPython 里deque的popleft()是 O(1)而列表pop(0)是 O(n)所以必須用deque。float(-inf)是 Python 表達負無窮的慣用方式用來初始化最大值。如果樹節(jié)點值范圍確定不超過10^9也可以直接用-10**18代替但-inf更通用、更語義化。三種語言對比下來你會發(fā)現(xiàn)核心邏輯完全一致差異只在語言自身的容器和語法細節(jié)上。說明 BFS 分層這個模式是語言無關的套路掌握了模板換語言只是照葫蘆畫瓢的事。4. 邊界條件、溢出與性能分析一道題能 AC只是及格把邊界情況想清楚才是寫代碼該有的狀態(tài)。這題別看簡單真要摳細節(jié)能摳出好幾個容易忽略的點。4.1 空樹與單節(jié)點題目默認root非空否則沒法討論層號。但工程習慣上仍然建議判空返回0表示“沒有層”。單節(jié)點樹的情況比較特殊只有一個根節(jié)點層號是1該層的和就是根節(jié)點值。即使這個值是-1000也正確返回1。這就是為什么maxSum不能用0初始化的意義所在。你可以手動跑一下代碼里第一層sum -1000-1000 Integer.MIN_VALUE成立于是ans 1結(jié)果正確。如果把maxSum初始化成0這個用例直接返回錯誤的初始ans。所以遇到二叉樹問題我習慣先問自己三個問題樹能不能為空節(jié)點值可能為負嗎層號從 0 還是 1 開始這三個問題的答案基本決定了初始化和邊界判斷怎么寫。4.2 負值節(jié)點與和溢出負值節(jié)點是這道題專門設的坑前面反復提過。再補充一個點節(jié)點值范圍是-10^5 Node.val 10^5二叉樹節(jié)點數(shù)最多10^4那么任意一層的元素和最大不會超過10^9int類型完全裝得下用Integer.MAX_VALUE和Integer.MIN_VALUE作為初始極值是安全的。但如果你在做同類題時發(fā)現(xiàn)節(jié)點值范圍和節(jié)點數(shù)量可能突破int上限比如10^9 * 10^5就別硬撐了直接把sum和maxSum都聲明成long。LeetCode 1161 里不需要但把這個意識培養(yǎng)起來是好事萬一改個輸入范圍就不至于翻車。順帶說一句sum在每層結(jié)束后用來比較完全可以在判斷完最大值之后不保留。因此每層重復使用同一個sum變量沒有任何問題不需要額外開數(shù)組存每層的和。這正是 BFS 逐層處理的空間優(yōu)勢——DFS 想拿到層和要么開數(shù)組要么額外維護而 BFS 用一個臨時變量就搞定。4.3 時間與空間復雜度時間復雜度是 O(n)其中 n 是二叉樹節(jié)點總數(shù)。理由很直接每個節(jié)點恰好入隊一次、出隊一次入隊出隊都是 O(1)不存在重復訪問。你可能注意到內(nèi)層循環(huán)次數(shù)是size但所有size加起來恰好等于 n所以總時間仍是 O(n)。空間復雜度是 O(w)w 是樹的最大寬度也就是隊列中同時存在的最大節(jié)點數(shù)。最壞情況是一棵滿二叉樹最底層的葉子節(jié)點數(shù)約為 n/2所以空間復雜度上界是 O(n)。如果樹退化成鏈表寬度為 1空間復雜度是 O(1)。和 DFS 的遞歸相比BFS 的空間消耗不隨樹的深度膨脹這是它處理深樹時的可靠之處。5. 常見錯誤與調(diào)試心得這部分是我最想聊的。很多同學覺得這道題代碼短隨便寫寫就過了但真到面試白板編程時細節(jié)錯誤一個接一個。我把自己刷題時踩過和見過別人踩的坑整理成了一份速查表再做一點詳細解釋。5.1 常見問題速查表錯誤現(xiàn)象根本原因解決辦法返回結(jié)果偏大或偏小層號不對sum沒有每層清零每層while內(nèi)、for前執(zhí)行sum 0樹全為負節(jié)點時結(jié)果恒為初始層號maxSum初始化為 0改為Integer.MIN_VALUE/INT_MIN/float(-inf)并列最大和時返回了更深層比較條件用了改用只允許更嚴格的最大值更新答案層號從 0 開始導致結(jié)果整體差 1沒有在進入每層時先level在外層循環(huán)開始處遞增層號保證首層為 1使用ArrayDeque存入null時報錯ArrayDeque不允許 null改用LinkedList或不向隊列中放入 null隊列永遠不為空程序死循環(huán)出隊后忘記pop/poll先取隊頭再彈出確保能消費掉當前節(jié)點把下一層節(jié)點混進當前層處理for循環(huán)條件用了動態(tài)queue.size()循環(huán)前用int size queue.size()固定次數(shù)這個表里每條都是真實踩過的坑不是我憑空編的。尤其第一和第二條幾乎每個初學 BFS 的人都會遇到至少一個。5.2 我個人踩過的坑講一個我印象最深的失誤最早的版本里我把sum定義在while循環(huán)外面然后想當然地以為“每層結(jié)束只要清零一次就行”。結(jié)果第一層累加完比較完最大值第二層開始前我確實清了零但清零點放在了maxSum比較之后。光看描述你可能覺得沒問題實際上第二層開始時隊列里除了第二層節(jié)點還殘留著第一層所有子節(jié)點已經(jīng)入隊但因為我的清零點晚了一步內(nèi)層for循環(huán)開始前sum還帶著上一層的殘留值。好在 LeetCode 的判題會明確告訴你錯在哪個用例我看了測試樣例[1, 7, 0, 7, -8, null, null]才明白是sum清零的位置不對。第二個坑是層號問題。一開始我天然認為和數(shù)組下標一樣從 0 開始計層于是level寫在了for循環(huán)后面結(jié)果返回的層號總是比預期小 1。后來我總結(jié)出一個習慣凡是題目里說“根節(jié)點是第 1 層”我就在外層while一開始先level這樣進入內(nèi)層循環(huán)時level正好表示當前處理的這層是哪一層清晰不容易錯。第三個坑是關于ArrayDeque的。有段時間我特別喜歡用ArrayDeque當隊列因為性能比LinkedList好。但在某道二叉樹的層序遍歷題里我往隊列里放了null作為層分隔符直接拋出NullPointerException。從那時起我給自己定了一條規(guī)矩如果 BFS 里有放null的需求就老老實實用LinkedList沒有放null的需求用ArrayDeque當然更高效。1161 這道題兩種都能用因為我們在循環(huán)內(nèi)通過node.left判空后才入隊隊列里不會出現(xiàn)null。6. 同類型題目與擴展思路1161 做完之后我不建議直接下一題。它的價值不在一道題本身而在于它把 BFS 分層模板的骨架完整呈現(xiàn)了一遍。這個模板可以遷移到很多 LeetCode 題目上花幾分鐘橫向?qū)Ρ纫幌卤葠烆^做十道新題還有用。6.1 對比最大寬度、最深層最左節(jié)點、右視圖BFS 分層模板最常見的變體是while (!queue.isEmpty()) { int size queue.size(); for (int i 0; i size; i) { // 在這里根據(jù)題目需求做處理 } }拿幾道經(jīng)典題來對照LeetCode 662 二叉樹最大寬度同樣需要分層但每層不僅要拿到節(jié)點還要記錄每個節(jié)點的位置索引寬度 最右索引 - 最左索引 1。模板不變額外維護索引。LeetCode 1302 層數(shù)最深葉子節(jié)點的和先 BFS 到最后一層再把最后一層的值加起來。實現(xiàn)上可以直接復用模板遍歷完所有層后記錄最后一層的sum。LeetCode 199 二叉樹的右視圖每層只取最右邊的節(jié)點值也就是for循環(huán)里i size - 1時的節(jié)點。模板幾乎原封不動。這幾道題和 1161 放在一起看你會發(fā)現(xiàn)它們的內(nèi)核完全一樣通過 size 快照精準鎖定每層的邊界然后在邊界內(nèi)做文章。區(qū)別只在于每層內(nèi)部要收集什么信息。把 1161 吃透再刷這幾道題會順暢很多。6.2 如果題目要求變了如果把題目改成“返回最大層內(nèi)元素和的那一層的和而不是層號”代碼只需改成最終返回maxSum其他邏輯完全不動。如果把“元素和”改成“平均值”也不難只要在每層循環(huán)結(jié)束時用sum除以size再參與比較即可。還有一種變體是如果元素和相同的層很多返回層號最大的那一層。這時候只需把比較條件從改成代碼里一行改動就能滿足。這提醒我們做題時一定要把題目里的“如果多個最大返回最小層號”這類限定讀清楚它直接決定了那個看似不起眼的運算符是還是。6.3 用“每層求和”模板去刷題我自己的經(jīng)驗是BFS 分層題想穩(wěn)定不失誤最好把模板背到肌肉記憶的程度。所謂“分層三件套”就是外層while、內(nèi)層for加 size 快照、每層結(jié)束后的業(yè)務邏輯。只要這三件套不亂代碼基本不會偏離正確答案太遠。最后分享一個小技巧遇到樹相關的題目先在草稿紙上畫一棵三層的簡單樹標出每一層的節(jié)點然后手動模擬 BFS 的入隊出隊過程。只要你能把“當前層有幾個節(jié)點、下一層有哪些節(jié)點”這層關系搞清楚代碼怎么寫都不會錯。我在帶新人刷題時經(jīng)常讓他們這么做效果比直接看題解好得多。