水题踩坑之迭代器

Posted on | | Visitors:

今天刷leetcode遇到一个题 Binary Tree Paths,打印出二叉树的所有路径，在写非递归解法的时候踩了一个容器迭代器的坑，记录一下。

以下是代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ret;
        stack<TreeNode*> st;
        if(root)st.push(root);
        TreeNode *tmp;
        vector<string>::iterator it;
        while(!st.empty())
        {
            int pushed = 0;
            tmp = st.top();
            
            if(ret.size()==0)
            {
                string s1;
                s1=to_string(tmp->val);
                ret.push_back(s1);
                it = ret.begin();
            }
            else
            {
                string &s2=*it;
                s2+="->";
                s2+=to_string(tmp->val);
            }
            
            st.pop();
            if(tmp->right){st.push(tmp->right);pushed++;}
            if(tmp->left){st.push(tmp->left);pushed++;}
            //有两个节点，则复制一份字符串
            if(pushed==2)
            {
                string s3(*it);
                //返回插入元素的迭代器
                it = ret.insert(it+1,s3);
                it--;
            }
            
            //没有子树，迭代器后移
            else if(pushed==0)it++;
        }
        return ret;
    }
};

思路是利用栈存放节点，在出栈的同时将该节点的子节点入栈，如果左右子树都有，那么需要将之前已打印过的字符串复制一份（因为重复的路径还会用到）。在这里复制路径的时候用的是 vector<type>.insert(iterator,const type &)，刚开始代码的 43-46 行是这样的：

1
2
3

string s3(*it);
ret.insert(it+1,s3);

然后提交的时候出现的 Runtime Error, 搞了半天，感觉可能是迭代器的锅。于是翻了一下《C++ Primer》，P273 9.9.3节讲了在顺序容器中添加或删除元素时可能会导致整个容器重新加载从而使迭代器失效，因此在容器中添加或者删除元素时要确保迭代器得到更新。书的后面还给出一个例子：

1
2
3
4
5
6
7

vector<int>::iterator first = v.begin(), last=v.end();
while(first!=last)
{
    first = v.insert(first,42);
    ++first;
}

上面的代码的行为是未定义的，因为插入操作后，last可能失效，因此需要每次重新计算end迭代器。

1
2
3
4
5
6
7

vector<int>::iterator first = v.begin();
while(first!=v.end())
{
    first = v.insert(first,42);
    ++first;
}