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

/*
描述
给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},
该二叉树层序遍历的结果是
[[3],[9,20],[15,7]]
输入：
{1,2}
返回值：
[[1],[2]]
示例2
输入：
{1,2,3,4,#,#,5}
返回值：
[[1],[2,3],[4,5]]
*/

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};


class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        if (root == nullptr) return resultArr;
        TreeNode* tmp;
        int d = 0;
        int curr_depth = 0;
        que.push(root);
        dep.push(d);
        while (!que.empty()) {
            tmp = que.front();
            que.pop();
            d = dep.front();
            dep.pop();
            // handle the output
            if (curr_depth < d) {
                // store the last layer's result and clear, preparing for the next layer's storage
                curr_depth = d;
                resultArr.push_back(layerArr);
                layerArr.clear();
                layerArr.push_back(tmp->val);
            }
            else {
                // curr_depth == d
                layerArr.push_back(tmp->val);

            }
            // handle the queues
            if (tmp->left) {
                que.push(tmp->left);
                dep.push(d + 1);
            }
            if (tmp->right) {
                que.push(tmp->right);
                dep.push(d + 1);
            }

        }
        resultArr.push_back(layerArr);      // add last layer's result
        return resultArr;
    }

private:
    vector<int> layerArr;
    vector<vector<int>> resultArr;
    queue<TreeNode*> que;
    queue<int> dep;
};