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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <queue>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        vector<vector<int>> ans;
        if (root==NULL) {
            return ans;
        }
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            vector<int> row;
            TreeNode* cur;
            int n = q.size();
            for (int i = 0; i < n; i++) {
                cur = q.front();
                q.pop();            //queue先进先出
                row.push_back(cur->val);
                if (cur->left) {
                    q.push(cur->left);
                }
                if (cur->right) {
                    q.push(cur->right);
                }
            }
            ans.push_back(row);
        }
        return ans;
    }
};

层序遍历，借助队列的先进先出，

队列使用方法： queue<class> name; name.push(class); name.front;//取首元素； name.pop;//先进先出；

思路：

1.每一次将一层的元素放到队列中，循环取出元素

2.将元素中的数值放入行vector中，此次循环次数为上次queue中的元素个数

3.元素数值放入vector中后，立即pop

4.访问当前元素值的子节点，非空则放入队列q中。

5.下次循环，取出下一层的所有元素。

6.下一层的所有元素，即你pop完当前层后，队列q中新加入的节点元素。

7.再次循环。

8.每次循环后，将同一行的vector放入整体的vector，最终返回大的vector