題目描述: 給定一棵二元樹的根節點,找到樹的最後一列(最深層)中最左邊的節點值。
解題思路: 使用 BFS(層序遍歷),但改為從右到左加入子節點。這樣每層最後被處理的節點就是最左邊的。當 BFS 結束時,最後一個被處理的節點即為最底層最左邊的節點。
或者更直觀地:標準 BFS 從左到右遍歷,記錄每層第一個節點值,最終結果為最後一層的第一個節點。
最簡潔的方式是從右到左 BFS:
時間複雜度:O(n) — 每個節點恰好被訪問一次。
空間複雜度:O(n) — 佇列最多儲存一層的節點,最壞情況(完美二元樹)為 n/2。
1. Initialize queue with root 2. While queue is not empty: a. Dequeue node, set result = node.val b. If node has right child, enqueue right child c. If node has left child, enqueue left child 3. Return result (last dequeued node = bottom-left)
標準 BFS + 每層追蹤:使用標準從左到右的 BFS,每層開始時記錄第一個節點的值。最後一層的第一個節點即為答案。時間 O(n),空間 O(n)。邏輯更直觀但需要額外的層級追蹤。
DFS + 最大深度追蹤:維護全域變數 maxDepth 和 result。DFS 時先訪問左子樹,再訪問右子樹。若當前深度超過 maxDepth,更新 maxDepth 和 result。時間 O(n),空間 O(h)(遞迴深度)。空間效率更優(平衡樹時 O(log n)),且邏輯簡潔。