leetcode 102:二叉树的层次遍历

一：队列

std::vector<std::vector<int>> levelOrder(TreeNode*root){
    std::vector<std::vector<int>> a;
    if(root==NULL)return a;

    std::deque<TreeNode*> q;
    std::vector<int> v;
    q.push_back(root);
    while(!q.empty()){
        int c=q.size();
        for(int i=0;i<c;i++){
            TreeNode *l=q.front();
            v.push_back(l->val);
            q.pop_front();
            if(l->left!=NULL)
                q.push_back(l->left);
            if(l->right!=NULL)
                q.push_back(l->right);
        }
        a.push_back(v);
        v.clear();
    }
    return a;
}

二、递归

void levelPush(TreeNode *l1,int level,std::vector<std::vector<int>> &a){
    if(l1==NULL)
        return;
    if(level==a.size()){
        std::vector<int> b;
        a.push_back(b);
    }
    a[level].push_back(l1->val);
    levelPush(l1->left,level+1,a);
    levelPush(l1->right,level+1,a);
}

std::vector<std::vector<int>> levelOrder(TreeNode*root){
    std::vector<std::vector<int>> a;
    levelPush(root,0,a);
    return a;
}