c - 找到等于总和的叶子路径（不是 BST）

Question

我正在尝试在 C 中编写一个递归函数，它接收二叉树中的根，并检查是否存在等于给定总和的 pathtoleaf。例如，它接收以下树中的第一个节点：

          1

   2              3

5       10       4    20

                            2

以下是 PathToLeaf 的示例：

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

以下不是 PathToLeaf：

• 1⟶2
• 1⟶3⟶20

如果路径存在，该函数应返回 1；如果不是，它应该返回 0。

在这棵树中，如果 sum=12，那么函数应该返回 1，因为路径 2⟶10；如果 sum=4，那么函数应该返回 0，因为唯一的路径 (1⟶3) 不会以叶子结尾。

我的大问题是我只能管理一个检查根叶路径的函数。

Answer 1

如果你有一个函数roottoleaf(const BST *tree, int target)，你的pathtoleaf(const BST *tree, int target)函数很容易遵循，不是吗，使用合适的树遍历？

int pathtoleaf(const BST *tree, int target)
{
    if (tree == NULL)
        return 0;
    else 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;
}

^{2021-07-04：更新以涵盖treeNULL 的情况。}