[LeetCode] Binary Tree Level Order Traversal 二叉樹層次周遊(DFS | BFS)

目錄：

1.binary tree level order traversal - 二叉樹層次周遊 bfs

2.binary tree level order traversal ii - 二叉樹層次周遊從低往高輸出 bfs

3.maximum depth of binary tree - 求二叉樹的深度 dfs

4.balanced binary tree - 判斷平衡二叉樹 dfs

5.path sum - 二叉樹路徑求和判斷dfs

題目概述：

given a binary tree, return the level order traversal

of its nodes' values. (ie, from left to right, level by level).

for example:

given binary tree <code>{3,9,20,#,#,15,7}</code>,

return its level order traversal as:

here's an example:

the above binary tree is serialized as <code>"{1,2,3,#,#,4,#,#,5}"</code>.

題目分析：

        本題考查的就是二叉樹的層次周遊，需要注意的是二叉樹用數組的表示方法，二叉樹的每層是從左到右存入數組的。方法包括：

        1.層次周遊。二維數組存儲數字和深度，輸出二維數組即可，過于複雜。

        2.通過隊列bfs廣度優先搜尋。

        3.通過dfs深度優先搜尋實作。

我的代碼：

代碼詳解：

        1.棧操作

        2.隊列操作

        3.二叉樹層次周遊如何使用隊列

        由于二叉樹是從左至右進行輸入，故層次周遊通過隊列存儲每層的結點，它存儲的順序也是前一個結點的左孩子結點、右孩子結點，依次順序進出隊列。

其他題目：

binary tree level order traversal ii

        層次周遊從低往root結點輸出，如 given binary tree <code>{3,9,20,#,#,15,7}</code>,

          return its level order traversal as:

        最簡單方法通過層次周遊bfs調用隊列後逆序倒置vector容器即可。

maximum depth of binary tree - 求二叉樹的深度

        常見方法通過bfs層次周遊計算二叉樹層數及深度或通過dfs計算二叉樹從root到leaf結點最長路徑及深度，在采用bsf代碼中可通過前面代碼進行修改，但錯誤：

                        [0,2,4,1,null,3,-1,5,1,null,6,null,8] output=5 excepted=4

       故采用dfs進行深度遞歸搜尋。代碼如下：

balanced binary tree - 判斷平衡二叉樹

        平衡二叉樹是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。參考前面的計算深度方法完成。

path sum - 二叉樹路徑求和判斷

given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.for example:

given the below binary tree and <code>sum = 22</code>,

return true, as there exist a root-to-leaf path <code>5-&gt;4-&gt;11-&gt;2</code> which sum is 22.

        該題主要考察dfs或bfs計算root到leaf結點路徑求和是否存在一條與sum相等的path。我采用dfs結合計算二叉樹深度完成，最初打算自定義isnode(*root,num)函數判斷，後來直接通過判斷每個結點是否是leaf且值為sum-前面結點。代碼如下：