[数据结构与算法]Leetcode 102.二叉树的层序遍历

102. 二叉树的层序遍历

给你一个二叉树，请你返回其按?层序遍历?得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层序遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

也算是结合百家所长，总结出来了自己的写法？

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root==nullptr){
            vector<vector<int>> ans;
            return ans;
        }
        queue<pair<TreeNode *,int>> q;
        vector<vector<int>> ans;
        q.emplace(pair<TreeNode *,int>(root,0));
        int maxlawer=1;
        ans.push_back({});
        while(!q.empty()){
            TreeNode* temp=q.front().first;
            int tempt=q.front().second;
            if(tempt+1>maxlawer){
                maxlawer=tempt+1;
                ans.push_back({});
            }
            if(temp->left){
                q.emplace(make_pair(temp->left,tempt+1));
            }
            if(temp->right){
                q.emplace(make_pair(temp->right,tempt+1));
            }
            ans[tempt].push_back(temp->val);
            q.pop();
        }
        return ans;
    }
};

思路为：

开创一个pair<TreeNode*,int>的队列，前者记录结点，后者记录他的层数。

然后进行简单的队列遍历，不断的把队列头结点的左右结点压入队列的同时把头结点pop掉。

用maxLayer记录当前ans的层数，如果需要就增加一层。