c++ - 关于 vector 元素的弹出

Question

给定一个二叉树和一个sum，以下代码用于查找所有等于特定sum 的根到叶路径。

class Solution {
public:
    void buildResult(std::vector< std::vector< int > >& result, std::vector< int >& ans, TreeNode* root, int sum) {
        if(!root)
            return;

        ans.push_back(root->val);
        if(root->val==sum && !root->left && !root->right)
            result.push_back(ans);
        buildResult(result, ans, root->left, sum-(root->val));
        buildResult(result, ans, root->right, sum-(root->val));
        ans.pop_back();
    }

    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        std::vector< vector< int > > result;
        std::vector< int > ans;

        if(!root)
            return result;

        buildResult(result, ans, root, sum);
        return result;
    }
};

以上代码有效并生成了预期的输出。但是，我不明白语句 ans.pop_back(); 的用法 - 我理解它是为了回溯，但是这个回溯到底是什么时候进行的？这些值甚至在检查它们是否位于有效路径之前就被插入到 vector ans 中。此外，pop_back() 的数量应该很多，具体取决于插入了多少导致总和不正确的数字。有人可以向我解释一下这个工作原理吗？

谢谢!

Answer 1

通过递归函数返回进行回溯。

递归函数在遍历树时通过将当前节点插入 ans 来记录其路径。当它到达叶子时，它会检查叶子的值，如果匹配，它会通过将 ans 插入 result 来记录它刚刚构建的路径。

您可以将 ans 视为指向当前节点的面包屑路径。递归函数每次进入树中的一个节点时，都会将当前节点的值压入ans中，当到达右叶时，breadcrumbs的尾部就是到叶节点的路径。

因此，递归函数通过返回离开它正在访问的当前节点。通过从递归调用返回，递归函数返回到它的父函数。但在从当前面包屑的尾部移除最后一个面包屑之前，恢复面包屑的轨迹以仅包含其父级的路径，这正是它要返回的位置。