[数据结构与算法]NC15 求二叉树的层序遍历

NC15 求二叉树的层序遍历

描述

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},

该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]
]

示例1

输入：{1,2}
返回值：[[1],[2]]

示例2

输入：{1,2,3,4,#,#,5}
返回值：[[1],[2,3],[4,5]]

3.队列实现——BFS遍历。（参考一位博主的讲解）
首先我们定义一个队列，然后将根节点入队，当队列不为空的时候，需要进行以下两个操作：
1）求出当前队列的长度大小len 。
2）取出队列前len个节点，每取出一个节点，就把对应节点的左右孩子入队（前提孩子不为空），然后重复这一过程直到队列为空后输出结果。

关键：通过size来记录分层！！注意代码中size的使用！！

博主大大视频链接

/**
 * 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> > res;
        if(!root) return res;
        queue<TreeNode *> qu;
        qu.push(root);
        while(!qu.empty()){
            int size = qu.size();//当前！注意是当前队列的大小！其实分析清楚就会发现，就是每一层的大小！
            vector<int> temp;
            while(size--){  //这里的size归零之后，就代表一层访问结束了！是通过size来分层的！
                TreeNode *node = qu.front();
                temp.push_back(node ->val);
                if(node ->left)
                    qu.push(node->left);
                if(node ->right) 
                    qu.push(node ->right);
                qu.pop();
            }
            res.push_back(temp);
        }
        return res;
    }
};