寒流來無聊窩在家裡寫 leetcode ，遇到了 101. Symmetric Tree，題目大意就是要判斷一棵二元樹是不是「對稱的」？一開始就想先把所有節點用 BFS 全部都列出來成一個 list，然後再根據二元樹的節點數一定會呈現「1+2+4+8+...」的模式、來把 list 切成 sublist。如果每個 sublist 都呈現對稱，就代表原始的 binary tree 就是對稱。
但可想而知這個方法行不通，因為不是所有二元樹都是滿節點，這樣會導致切 sublist 的時候就發生錯誤。這個時候靈光一閃：當初旁聽資料結構時有講到另外一個 DFS，可以選擇對二元樹 先向左 or 先向右 地往下優先走訪。
如果向左dfs與向右dfs出來的結果都一樣，就代表這棵二元樹是對稱的～
所以我說什麼是 BFS 與 DFS？
其實就是針對二元樹每一個節點，可以有的不同走訪方式～
廣度優先搜尋 Breadth-First Search, BFS
直覺的圖示就是一層一層剝洋蔥的方式來走訪節點， 上圖返回的結果就會是 [0, 1, 2, 3, 4, 5, 6]
深度優先搜尋 Depth-First Search, DFS
走訪方式改為優先向下鑽研，下圖的例子是選擇「先往左節點」向下鑽研，因此返回的結果會是 [0, 1, 3, 4, 2, 5, 6]
BFS Approach: Queue
為了使用 BFS走訪，我們必須使用 queue(佇列)，核心概念為利用它 先進先出FIFO 的特性（就跟你排隊買東西一樣）。
首先，我們把 root 放到 queue 中，dequeue 就把該節點的 value 放入 result中，並且規定只要 dequeue 的時候、就要把該節點的左右子節點也放到 queue 中(先放左、在放右)，當然如果子節點是空值就不需要放入。
最後，寫個 while loop 規定只要 queue 中還有值，就一直 dequeue、直到裡面完全沒有值，流程圖可參考以下：
程式碼實作爲以下，記得 r 輸入圍剛剛上面的範例，輸出結果即為 [1,2,2,3,4,4,3]
# 輸出結果
[1, 2, 2, 3, 4, 4, 3]DFS Approach: Stack
使用 DFS走訪，我們必須使用 stack(堆疊)，核心概念為利用它 先進後出FILO 的特性（就像碟碗盤一樣）
首先，一樣把 root 放到 stack 中，然後在 de-stack 時把該 node 的值放入 result 中。這時要注意的是：de-stack 一樣要同時把開node的左、右子節點放入 stack 中，但這時 先放左 或 先放右 會影響向下走往的方向。記得：
先放左，則走訪方式為向右下方DFS
先放右，則走訪方式為向左下方DFS
所以聰明的你想一下～我們應該要先放左還是先放右？
對～我們要 先放右結點 喔，這樣才是向左DFS，可參考以下：
程式碼中我把向左鑽、向右鑽都寫出來了，可以看出差別就只在於每次放入 stack 中是先放左子節點還是右子節點。
另外也可以看出，我一開始的例子 r 本身就是一個「對稱」的二元樹，所以不管往哪邊dfs結果都一樣會是 [1,2,3,4,2,4,3]
# 輸出結果
[1,2,3,4,2,4,3]
[1,2,3,4,2,4,3]
