Binary Tree Level Order Traversal

思路比较简单，典型的宽度优先遍历，但是在使用vector的时候出现了些问题。先上ac代码：

    vector<vector<int> > levelOrder(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function

        vector<vector<int> > result;
        if(root == NULL)
            return result;
        result.clear();
        vector<int> tmp;
        vector<TreeNode*> nodeVec;
        nodeVec.reserve(1000);
        nodeVec.push_back(root);
        vector<TreeNode*>::iterator head = nodeVec.begin(), tail = nodeVec.end()-1;
        while(!nodeVec.empty()){
            tmp.clear();
            while(head <= tail){
                tmp.push_back((*head)->val);
                if((*head)->left != NULL)
                    nodeVec.push_back((*head)->left);
                if((*head)->right != NULL)
                    nodeVec.push_back((*head)->right);
                head++;
            }
            result.push_back(tmp);
            nodeVec.erase(nodeVec.begin(), head);
            head = nodeVec.begin();
            tail = nodeVec.end()-1;
        }
        return result;
    }

出现的问题需要从下面这小段代码说起：

    vector<int> v;
//    v.reserve(100);
    v.push_back(1);
    vector<int>::iterator i = v.begin();
    cout<<*i<<endl;
    v.push_back(2);
    cout<<*i<<endl;
    list<int> l;
    l.push_back(1);
    list<int>::iterator ii = l.begin();
    cout<<*ii<<endl;
    l.push_back(2);
    cout<<*ii<<endl;
    system("pause");
    return 0;

vector在push_back之后，由于最开始申请的空间不足，所以vector重新申请和分配空间，begin获得的指针也发生变化，所以第二次输出*i的时候每次输出的值都不相同。

为了避免这样的问题，可以改用list，这也是list和vector的区别之一，list不需要连续的空间，所以不需要整体全部申请空间。

另外一种解决方法是最开始就为vector分配足够的空间，比如上面的语句v.reserve(100).