[LeetCode] 513. Find Bottom Left Tree Value

Given a binary tree, find the leftmost value in the last row of the tree.

找出上圖 最下層 最左邊的node 

這題一開始覺得應該很簡單 DFS 就搞定了.  事實上 BFS應該更為直接易懂.
在dfs pre-order的過程中對於 遞迴調用 non-local 值 的理解可說是一知半解
最後只好參考網路大神的解 用list 來做.

line 3: 用一個list 紀錄 值與深度
line 5: 沒東西 回退上層
line 6: 這裡是關鍵 只有目前傳進來的深度 大於 已知搜索深度 才更新 list
line 9 -10 : 如果題目問最右邊的值 把這兩行對調一下 就是結果了
line 11: 傳1進去, 定root所在層為1