树结构相关算法实例-递归方法遍历路径

在数据结构这门课程中，树结构是最重要的数据结构之一，有比较多的相关算法，比较有名的有：1、树的递归和非递归遍历；2、二叉搜索树的搜索过程；3、AVL树的构建过程；4、树的深度遍历（DFS）和宽度遍历（BFS）算法；5、其他更多的基于树结构的算法。树结构是图结构的基础，在实际应用中也有很多的问题基于树数据结构去建模。更多树结构的相关算法可以参考本文最后的链接，后面有机会也会进一步补充更多的相关算法。

今天要介绍的是一个树结构的一个中等难度左右的算法，即check一颗二叉树从根节点出发到叶子节点的路径上所有节点的和是否等于一个预先设定的值。

在这里介绍两种思路：1、通过递归遍历树结构找到所有的从根节点到叶子节点的路径，这些路径作为候选，一条一条路径check是否满足条件，如果满足可以将路径打印出来；2、通过递归程序直接判断是否存在这样的路径，这种条件下只返回true或false，不能打印出满足条件的路径。

下面主要介绍第一种算法思路（第二种代码思路请参考本文最后的链接），其主要代码如下所示，这里需要特殊说明的是c++中参数的传递技巧，如下面的代码中，path是普通变量，而all_paths是引用变量。普通变量在每一函数调用时会通过拷贝重新生成一个对象，而引用变量在所有递归调用过程中指向同一个数据变量。

//通过先序遍历求得所有从根节点到叶子节点的路径，然后去判断是否存在sum为target的值
void hasPathSumRecursive(TreeNode* root, std::vector<int> path, std::vector<std::vector<int>>&all_paths)
{
    if(root){
        path.push_back(root->val);
    }else{
        return;
    }
    if(root->left){
        hasPathSumRecursive(root->left, path, all_paths);
    }if(root->right)
    {
        hasPathSumRecursive(root->right, path, all_paths);
    }
    if(!root->left && !root->right){
        all_paths.push_back(path);
    }
}

bool hasPathSum(TreeNode* root, int targetSum) {
    std::vector<int> path;
    std::vector<std::vector<int>>all_paths_;
    hasPathSumRecursive(root, path, all_paths_);
    for(int i = 0; i < all_paths_.size(); i++)
    {
        int sum = 0;
        for(int j = 0; j < all_paths_[i].size(); j++)
        {
            sum += all_paths_[i][j];
        }
        if(sum == targetSum)
        {
            std::cout << "the satisfied path is ....:" << std::endl;
            for(int j = 0; j < all_paths_[i].size(); j++)
            {
                std::cout << all_paths_[i][j] << " " ;
            }
            return true;
        }
    }
    return false;
}

两个算法完整的代码请参考链接： data-structures-algorithms/trees/path-sum.cpp at main · kindlytree/data-structures-algorithms (github.com)