找到等於總和的葉子的路徑（非BST）

Question

我想在C中寫一個遞歸函數，它接收二叉樹中的根，並檢查是否存在等於給定總和的pathtoleaf。例如，它接收在下列樹中的第一個節點：

  1 

    2    3 

5  10  4 20 

          2 

以下是PathToLeaf的例子：

• 1⟶2⟶10
• 2⟶5
• 20⟶2

The followi納克不PathToLeaf：

• 1⟶2
• 1⟶3⟶20

如果路徑存在，則該函數將返回1;如果不是，則返回0.

在這棵樹中，如果sum = 12，那麼函數應該返回1，因爲路徑2⟶10;如果sum = 4，那麼函數應該返回0，因爲唯一路徑（1⟶3）不會以葉結尾。

這裏我最大的問題是我只能管理一個檢查roottoleaf路徑的函數。

Answer 1

如果你有一個功能roottoleaf(const BST *tree, int target)，你的pathtoleaf(const BST *tree, int target)功能很容易，不是嗎，使用適當的遍歷樹？

int pathtoleaf(const BST *tree, int target) 
{ 
    if (roottoleaf(tree, target)) 
     return 1; 
    else if (pathtoleaf(tree->left, target)) 
     return 1; 
    else if (pathtoleaf(tree->right, target)) 
     return 1; 
    else 
     return 0; 
}