leetcode 1430 二叉树路径验证题解指南

最近在刷LeetCode時，又碰上了那道二叉樹路徑驗證題（1430），腦海裡浮現出第一次解題時的手忙腳亂。那會兒在咖啡館盯著螢幕，鍵盤敲得飛快，卻總卡在邊界條件上——樹空了序列還沒完，或是葉子節點沒對上序列尾端，結果提交了三次才過。這種題目看似簡單，實則暗藏玄機，考驗你對樹結構的直覺，還有遞歸那點細膩功夫。

題目要求驗證一個給定序列是否代表從根到葉子的完整路徑。聽起來直白吧？輸入一棵二叉樹和一個整數陣列，你得確保序列從根開始，一路往下匹配節點值，直到某個葉子節點結束。但魔鬼在細節裡：序列長度必須等於路徑深度，每個節點值得對上序列位置，還得確認終點是葉子（沒左右子節點）。記得有次我用BFS硬幹，結果漏了葉子檢查，白費半小時調試。後來轉用DFS遞歸，才豁然開朗——從根出發，逐層比對，遇到空節點或值不匹配就提前返回，只有當當前節點是葉子且序列耗盡才算成功。

解法核心在於遞歸函數的設計。我習慣定義個輔助函數，參數帶上當前節點和序列索引。進去先看節點是否空值，或索引越界——這些是失敗條件。接著比對節點值與序列值，不相等直接跳出。關鍵來了：如果當前節點是葉子（左右子皆空），且索引正好在序列末尾，那就是找到合法路徑；否則，繼續遞歸遍歷左子樹或右子樹。這裡有個優化點，用OR操作處理左右分支，任一成功就返回真，避免多餘計算。時間複雜度O(n)，n是節點數，空間複雜度O(h)，h是樹高，最壞情況樹退化成鏈表。

實戰中常見坑不少。新手常忘檢查葉子條件，結果路徑半途就誤判成功；或是序列長度不足時沒提前終止，導致空指針異常。我建議寫完碼後，手動跑幾個邊界用例：空樹配空序列該成功，單節點樹序列長度為1才合法，序列中途值錯位該失敗。用單元測試驗證，比提交後看錯誤提示省時得多。另外，遞歸雖優雅，但大樹可能棧溢出，面試時可提迭代解法用棧模擬，不過這題數據規模通常遞歸就夠了。

解這類題，練的是對樹遍歷的本能反應。每次重刷，我都會問自己：遞歸終止條件夠嚴謹嗎？分支合併邏輯是否高效？漸漸地，這種思維成了肌肉記憶。LeetCode路上，每道題都是打磨細節的砂紙，磨掉急躁，留下耐心。下次你再遇1430，試著閉眼勾勒遞歸樹，或許會發現它比想像中溫柔。