題目敘述
題目會給定一棵二元樹的根結點，要求我們找出這棵二元樹最後一層最左邊的值。
測試範例
Example 1:
Input: root = [2,1,3]
Output: 1
Example 2:
Input: root = [1,2,3,4,null,5,6,null,null,7]
Output: 7
約束條件
Constraints:
- The number of nodes in the tree is in the range
[1, 10^4].
節點總數量界於1~一萬之間。
-2^31 <= Node.val <= 2^31- 1
所有節點值都落在32bits整數範圍內。
演算法 BFS 或 DFS
其實和前面介紹過的那題 二元樹的右側視角 很像。
這題題目所求為 二元樹最後一層最左邊的值。
那就依照題意，廣度優先BFS或深度優先DFS拜訪到最後一層，紀錄左手邊第一個遇到的節點值即可。
程式碼 BFS
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import deque
class Solution:
def findBottomLeftValue(self, root: TreeNode) -> int:
traversal_queue = [ root ]
bottom_left = root
while traversal_queue:
next_level = []
for idx, node in enumerate(traversal_queue):
if not idx:
# update bottom left as the first node on current level
bottom_left = node
# add child node to next level traversal queue if they exist
if node.left:
next_level.append( node.left )
if node.right:
next_level.append( node.right )
traversal_queue = next_level
return bottom_left.val
複雜度分析
時間複雜度:
BFS廣度優先拜訪整棵樹，每個節點至多拜訪一次。所需時間為O(n)
空間複雜度:
BFS quque所需成本為O(n)，最大成本落在最後一層。
程式碼 DFS
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
def finder(node, level):
if not node:
return
if level > finder.level:
finder.bottom_left = node.val
finder.level = level
finder(node.left, level+1)
finder(node.right, level+1)
return
# -------------------------------
finder.bottom_left = None
finder.level = 0
finder(node=root, level=1)
return finder.bottom_left
時間複雜度:
DFS廣度優先拜訪整棵樹，每個節點至多拜訪一次。所需時間為O(n)
空間複雜度:
DFS recursion stack所需成本為O(n)，最大深度為整棵樹的最大樹高。
關鍵知識點
條條大路通羅馬，只要掌握基本原理，遇到新的題目也能根據基本的圖論演算法DFS、BFS配合題意的需求去構建出解題的演算法。
另外，還有一個衍伸題，假如題目問我們最後一層最右邊的值? 要怎麼改?
也很容易，把拜訪順序改成從右到左，取最後一層第一個遇到的節點值，就可以囉！
Reference:
