題目

注意題目的意思是要從頭結(jié)點(diǎn)到葉子的路徑。

這個沒辦法只能遍歷每一條路徑然后判斷。
不過因?yàn)槭菢?，所以我們可以方便的使用遞歸和回溯。

因?yàn)槲覀円蛴〕鰜硭晕覀円４嬉粋€path 路徑，儲存當(dāng)前路徑的節(jié)點(diǎn)。

路徑和sum是同時更新的。

• 加入當(dāng)前節(jié)點(diǎn)：
  path.push_back(phead->data); cur_sum += phead->data;

• 刪除當(dāng)前節(jié)點(diǎn)
  path.pop_back(); cur_sum -= phead->data;
  上面這句就是回溯的體現(xiàn)。

• 遞歸實(shí)現(xiàn)遍歷

    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);

• 在程序的最開始進(jìn)行判斷，打?。?/li>

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

• 小函數(shù)：

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;
}

文章參考何海濤大神文章