Leetcode之旅|落葉歸根

圖片來源，侵刪

1. 題目描述

Find Bottom Left Tree Value

　　顧名思義，返回最左邊的葉子節點。

比如：

2 / 1 3

返回1。

而比如：

1 / 2 3 / / 4 5 6 / 7

則返回7

2. 解題思路

　　看到這題第一反應就是：BFS啊！沒辦法，腦子裡不由自主地回想起多年前coursera課上老師的諄諄教誨。假設以根節點為中心，其餘各層節點可看做一層一層的同心環，高度相同的節點在同一環上，找到最後一環的第一個節點即可。這可不就是BFS么哈哈！！！

　　題目要求的是找最左邊的葉子節點，所以這裡採用的是FIFO的數據結構，即先進先出，這樣能保證每次進隊列的節點的父節點是從最左邊開始。每層遍歷時，保存最左邊的節點為res，遍歷完成後返回res。代碼如下：

3. 代碼

class Solution: def findBottomLeftValue(self, root): """ :type root: TreeNode :rtype: int """ if not root.left and not root.right: return root.val queue = [root] while queue: q = queue cur = [] res = q[0].val while q: # 這裡是將q實現為一個FIFO，即先進先出 # 達到將高度相同的節點從左到右依次入隊列的效果 a = q.pop(0) if a.left: cur.append(a.left) if a.right: cur.append(a.right) queue = cur return res

4. 總結

　　這道題雖然是medium難度，但其實比較簡單，對我而言的意義主要還是終於開始慢慢理解這類型數據結構的操作，以及慢慢摸索到解答這類題目的思路入口了。