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

#C++版本的简单实现

1. 算法思路

• 建立两个队列Q1,Q2;Q2初始化为root，即根节点。
• Q1存储当前层序的数据；Q2存储下一层的数据。
• 遍历Q1，遍历后每次都取出头尾数据；当Q1为空时，Q1与Q2交换队列。
• 终止条件，Q2为空队列。

2. 第一次自己搞定，虽然思路写法都不高级，但还是分享了出来

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        
        vector<vector<int> > v;
        if(root==NULL)  //判空
            return v;
        queue<TreeNode*> Q1;
        queue<TreeNode*> Q2;
        
        TreeNode *p;  
        Q2.push(root);
        
        while(!Q2.empty())
        {
        vector<int> v1;
        if(Q1.empty())
                Q1.swap(Q2);
        while(!Q1.empty())
        {
            p=Q1.front();
            v1.push_back(p->val);
            Q1.pop();
            if(p->left)
                Q2.push(p->left);
            if(p->right)
                Q2.push(p->right);
        }
        v.push_back(v1);
        }

        return v;
    }
};