Description
給定一棵二元樹的根節點，回傳樹的最底層最左邊的值。
Example:
Input: root = [2,1,3] Output: 1
Intuition#
BFS 從右到左遍歷，最後一個訪問的節點就是最底層最左邊的。
- 「最底層最左邊」= 最大深度的第一個節點
- BFS 層序遍歷每層第一個就是最左；或者反向 BFS（先右後左），最後一個就是答案
- DFS 也可以，記錄最大深度對應的第一個節點
Approaches#
1: BFS 層序遍歷#
- 概念: 標準 BFS，每層記錄第一個節點的值，最後一層的第一個就是答案
- 時間複雜度:
O(n) - 空間複雜度:
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 從右到左#
- 概念: 每次先加右子再加左子，最後出隊的就是最底層最左邊的節點
- 時間複雜度:
O(n) - 空間複雜度:
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
}
}為什麼從右到左 BFS 最後一個就是答案？
BFS 逐層遍歷。如果每層先加右子再加左子，那麼同一層中左邊的節點會排在右邊的後面。整棵樹最後被訪問的節點，就是最深層的最左邊節點。這個技巧省去了按層分隔的邏輯。
🔑 Takeaways#
- Pattern: 找最底層某位置的節點，BFS 是最直覺的方法
- 關鍵技巧: 反向 BFS（先右後左）讓最後出隊的就是目標，程式碼非常簡潔