面试题：C++ 中 Lambda 表达式递归在复杂数据结构遍历中的应用

数据结构定义

#include <vector>
#include <iostream>

struct TreeNode {
    int val;
    std::vector<TreeNode*> children;
    TreeNode(int x) : val(x) {}
};

DFS 实现

std::vector<std::vector<int>> findPaths(TreeNode* root, int targetSum) {
    std::vector<std::vector<int>> result;
    std::vector<int> path;
    auto dfs = [&result, &path, targetSum](const auto& self, TreeNode* node, int currentSum) -> void {
        if (!node) return;
        path.push_back(node->val);
        currentSum += node->val;
        if (currentSum == targetSum &&!node->children.size()) {
            result.push_back(path);
        }
        for (TreeNode* child : node->children) {
            self(self, child, currentSum);
        }
        path.pop_back();
    };
    dfs(dfs, root, 0);
    return result;
}

挑战及解决方法
- Lambda 表达式递归调用的作用域：
  - 挑战：Lambda 表达式默认不能递归调用自身，因为它在定义时还没有名称。
  - 解决：使用auto类型的变量来存储 Lambda 表达式，并在递归调用时将该变量作为参数传递给自己，例如auto dfs = [&result, &path, targetSum](const auto& self, TreeNode* node, int currentSum) -> void {... }; dfs(dfs, root, 0);。这里self是对 Lambda 表达式自身的引用，通过这种方式实现了递归调用。
- 捕获变量的处理：
  - 挑战：在 Lambda 表达式中捕获外部变量时，需要注意捕获方式。如果捕获不当，可能会导致意外的行为，比如捕获了局部变量的副本，而在递归过程中这些副本没有正确更新。
  - 解决：在这个实现中，我们采用了引用捕获[&result, &path, targetSum]，这样result和path是对外部变量的引用，在递归过程中对path的修改会反映到外部，并且targetSum始终是同一个值，不会因为递归产生新的副本。同时，currentSum作为递归函数的参数传递，避免了捕获可能带来的问题。

在主函数中可以这样测试：

int main() {
    TreeNode* root = new TreeNode(5);
    root->children.push_back(new TreeNode(4));
    root->children.push_back(new TreeNode(8));
    root->children[0]->children.push_back(new TreeNode(11));
    root->children[0]->children[0]->children.push_back(new TreeNode(7));
    root->children[0]->children[0]->children.push_back(new TreeNode(2));
    root->children[1]->children.push_back(new TreeNode(13));
    root->children[1]->children.push_back(new TreeNode(4));
    root->children[1]->children[1]->children.push_back(new TreeNode(5));
    root->children[1]->children[1]->children.push_back(new TreeNode(1));

    std::vector<std::vector<int>> paths = findPaths(root, 22);
    for (const auto& path : paths) {
        for (int num : path) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}

这样就实现了使用 C++ Lambda 表达式递归对树形结构进行深度优先搜索，找到所有节点值之和为特定值的路径，并以std::vector<std::vector<int>>返回这些路径。

星途面试题库

面试题：C++ 中 Lambda 表达式递归在复杂数据结构遍历中的应用

知识考点

面试题答案