Binary Tree Level Order Traversal-白红宇

Binary Tree Level Order Traversal

阅读量：5776 次

发布时间：2019-06-18

本文共 1412 字，大约阅读时间需要 4 分钟。

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

vector
     
      
        > levelOrder(TreeNode *root) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        vector
       
        
          > result;        if(root == NULL)            return result;        result.clear();        vector
         
           tmp;        vector
          
            nodeVec; nodeVec.reserve(1000); nodeVec.push_back(root); vector
           
            ::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
     
       v;//    v.reserve(100);    v.push_back(1);    vector
      
       ::iterator i = v.begin();    cout<<*i<

l; l.push_back(1); list

::iterator ii = l.begin(); cout<<*ii<

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

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

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

转载于:https://www.cnblogs.com/waruzhi/p/3346806.html

你可能感兴趣的文章