题解 | #求二叉树的层序遍历#

题解一：递归(前序遍历)
主要思路：前序遍历，中、左、右
左边的节点一定先于右边节点遍历到，加入至对应的数组中，满足层序遍历的要求；
要点：
1、利用一个level变量标记当前递归的深度，将节点的值push到当前深度的数组的后面；
2、level变量大于res数组的size，说明第一次进入二叉树本层，对res扩容；

扩展：
前序：中、左、右
中序：左、中、右
后续：左、右、中
三种遍历都是左边节点一定比右边节点先遍历到，那么push_back至对应深度的数组次序也一定与层次遍历一致；所以针对此方法，中序、后序一样可以实现层次遍历。

对示例1模拟前序遍历，如下图所示：

复杂度分析:
时间复杂度:O(n),n为二叉树的节点数；
空间复杂度:O(n),除去存储节点值的空间，最差情况：二叉树退化成链表，递归深度为N；

实现如下:

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    //前序遍历模板；
    void f(TreeNode* root,int level,vector<vector<int>> &res){
        if(!root)return ;
        if(level>=res.size()){//最新的深度，申请一个数组存储；
            res.push_back(vector<int> {});
        }
        res[level].push_back(root->val);
        f(root->left,level+1,res);//遍历左子树;
        f(root->right,level+1,res);//遍历右子树；
    }

    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        vector<vector<int>> res;//存储最终结果；
        f(root,0,res);//前序遍历；
        return res;//返回结果；
    }
};

题解二：BFS(迭代)
主要思路：广度优先
如下图所示：一层一层的遍历二叉树，
1、遍历到一个节点，将左右个孩子加入队列；
2、一次遍历二叉树的一层；
3、怎么确定能遍历一层：每次遍历队列，先记录队列的大小size，出队size次，这些值即为一层，存入res数组，并通过1、2将下一层的节点存入队列；

对示例1模拟前序遍历，如下图所示：

复杂度分析：
时间复杂度：O(n),每个点进队出队各一次，遍历了整个二叉树。
空间复杂度：O(n),队列中元素的个数不超过 n 个，所以空间复杂度为 O(n)。

实现如下:

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        vector<vector<int> > vv;
        if(!root){
            return vv;//二叉树为空
        }
        queue<TreeNode*> qq;//队列存放相邻两层节点；
        qq.push(root);
        while(!qq.empty()){
            vector<int> tempv;
            int size=qq.size();
            for(int i=0;i<size;++i){//将一层的节点size出队；
                TreeNode* tt=qq.front();
                qq.pop();
                tempv.push_back(tt->val);
                //将下一层的节点入队；
                if(tt->left)qq.push(tt->left);
                if(tt->right)qq.push(tt->right);
            }
            vv.push_back(tempv);//加入将要返回的数组中；
        }
        return vv;//返回最终结果
    }
};

二叉树遍历相关题目集:
二叉树中是否存在节点和为指定值的路径
二叉树的最大深度
二叉树中序遍历