Medium
513. Find Bottom Left Tree Value
treedepth-first-searchbreadth-first-searchbinary-tree
解題說明
Find Bottom Left Tree Value
題目描述： 給定一棵二元樹的根節點，找到樹的最後一列（最深層）中最左邊的節點值。
解題思路： 使用 BFS（層序遍歷），但改為從右到左加入子節點。這樣每層最後被處理的節點就是最左邊的。當 BFS 結束時，最後一個被處理的節點即為最底層最左邊的節點。
或者更直觀地：標準 BFS 從左到右遍歷，記錄每層第一個節點值，最終結果為最後一層的第一個節點。
最簡潔的方式是從右到左 BFS：
- 將根節點入佇列。
- 每次取出節點時，先加入右子再加入左子。
- BFS 結束時，最後被取出的節點就是答案。
C++ 解法
複雜度分析
時間複雜度：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)），且邏輯簡潔。
延伸思考
- 「從右到左 BFS」的技巧為什麼能保證最後處理的是最底層最左邊的節點？能否用數學歸納法證明？
- 若要找最底層最右邊的節點，如何修改算法？
- DFS 方法中「先左後右」的遍歷順序至關重要，如果改為「先右後左」會得到什麼結果？