[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-前面结点。代码如下：