給定一棵二元樹的根節點，回傳樹的最底層最左邊的值。
Example:
Input: root = [2,1,3] Output: 1
Intuition
TIP
BFS 從右到左遍歷，最後一個訪問的節點就是最底層最左邊的。
- 「最底層最左邊」= 最大深度的第一個節點
- BFS 層序遍歷每層第一個就是最左；或者反向 BFS（先右後左），最後一個就是答案
- DFS 也可以，記錄最大深度對應的第一個節點
Approaches
1. BFS Level-order — O(n) / O(n)
- Idea: 標準 BFS，每層記錄第一個節點的值，最後一層的第一個就是答案
- Time:
O(n) - Space:
O(n)
class Solution {
fun findBottomLeftValue(root: TreeNode?): Int {
var result = root!!.`val`
val queue: Queue<TreeNode> = LinkedList()
queue.offer(root)
while (queue.isNotEmpty()) {
val size = queue.size
for (i in 0 until size) {
val node = queue.poll()
if (i == 0) result = node.`val`
node.left?.let { queue.offer(it) }
node.right?.let { queue.offer(it) }
}
}
return result
}
}⭐ 2. BFS Right-to-Left — O(n) / O(n)
- Idea: 每次先加右子再加左子，最後出隊的就是最底層最左邊的節點
- Time:
O(n) - Space:
O(n)
class Solution {
fun findBottomLeftValue(root: TreeNode?): Int {
var result = root!!.`val`
val queue: Queue<TreeNode> = LinkedList()
queue.offer(root)
while (queue.isNotEmpty()) {
val node = queue.poll()
result = node.`val`
node.right?.let { queue.offer(it) }
node.left?.let { queue.offer(it) }
}
return result
}
}Why right-to-left BFS yields the answer last?
BFS 逐層遍歷。如果每層先加右子再加左子，那麼同一層中左邊的節點會排在右邊的後面。整棵樹最後被訪問的節點，就是最深層的最左邊節點。這個技巧省去了按層分隔的邏輯。
🔑 Takeaways
- Pattern: 找最底層某位置的節點，BFS 是最直覺的方法
- Key trick: 反向 BFS（先右後左）讓最後出隊的就是目標，程式碼非常簡潔