树中和为定值的路径

题目

注意题目的意思是要从头结点到叶子的路径。

这个没办法只能遍历每一条路径然后判断。
不过因为是树，所以我们可以方便的使用递归和回溯。

因为我们要打印出来所以我们要保存一个path 路径，储存当前路径的节点。

路径和sum是同时更新的。

• 加入当前节点：
  path.push_back(phead->data); cur_sum += phead->data;

• 删除当前节点
  path.pop_back(); cur_sum -= phead->data;
  上面这句就是回溯的体现。

• 递归实现遍历

    if (phead->left)
        find_path(phead->left, sum,cur_sum, path);
    //path.pop_back();

    if (phead->right)
        find_path(phead->right, sum,cur_sum, path);

• 在程序的最开始进行判断，打印：

    if (isLeaf(phead) && cur_sum == sum)
        print_vec(path);

• 小函数：

bool isLeaf(treeNode* node)
{
    return (node->left==NULL || node->right==NULL);
}
void print_vec(std::vector<int> path)
{
    auto beg = path.begin();
    for (beg; beg != path.end(); beg++)
        std::cout << *beg<<" ";
}

总的：

#include <vector>
struct treeNode
{
    int data;
    treeNode* left;
    treeNode* right;
};
bool isLeaf(treeNode* node)
{
    return (node->left==NULL || node->right==NULL);
}
void print_vec(std::vector<int> path)
{
    auto beg = path.begin();
    for (beg; beg != path.end(); beg++)
        std::cout << *beg<<" ";
}

void find_path(treeNode* tree, int sum,int cur_sum,std::vector<int> path)
{
    //int cur_sum=0;
    treeNode* phead=tree;
    if (!tree)
        return;
    path.push_back(phead->data);
    cur_sum += phead->data;

    if (isLeaf(phead) && cur_sum == sum)
        print_vec(path);

    if (phead->left)
        find_path(phead->left, sum,cur_sum, path);
    //path.pop_back();

    if (phead->right)
        find_path(phead->right, sum,cur_sum, path);

    path.pop_back();
    cur_sum -= phead->data;
}

文章参考何海涛大神文章