检查二叉树的路径是否等于给定的总和

Question

我在寻找解决方案时遇到问题:

“给定一棵二叉树(每个节点都有一个 int 值)和一个和，如果树的路径等于给定的和(从节点到叶子，不一定是根)，则返回 1 )，否则返回 0"。

我做过一个类似的问题，路径必须从根开始。但在这里，问题指出路径可以从任何地方开始，只要它以叶子结束即可..

尝试在线搜索解决方案，但我发现一些解决方案只能通过使用缓冲区来工作。

如果没有缓冲区，有没有可能的解决方案？

提前致谢!

(首选 C、C++ 语法甚至伪代码 ^.^``)

这是我的第一次尝试:

int hasPathSum(Tree tr, int sum){
return hasPathSumRec(tr.root, sum, 0);
}


int hasPathSumRec(TNode* node, int sum, int current){

int num1, num2;
current += node->data;
if (current > sum)
    current = 0;

if (node->left == NULL && node->right == NULL){
    if (current == sum)
        return 1;
    return 0;
}
else if (node->left == NULL){
    return hasPathSumRec(node->right, sum, current);

}
else if (node->right == NULL){
    return hasPathSumRec(node->left, sum, current);
}
else{
    num1=hasPathSumRec(node->left, sum, current);
    num2=hasPathSumRec(node->right, sum, current);

    if (num1 > 0 || num2 > 0)
        return 1;
    else
        return 0;
}
}

这是第二个:(但它没有经过所有节点，所以不好..)

int hasPathSum(Tree tr, int sum){
return hasPathSumRec(tr.root, sum, 0);
}

int hasPathSumRec(TNode* node, int sum, int current){
int num, num1, num2;


num = node->data;
current = num + current;

if (current > sum)
    current = num;


if (node->left == NULL && node->right == NULL){
    if (node->data == sum || current == sum)
        return 1;
    else
        return 0;
}
else if (node->left == NULL){
    num2 = node->right->data;
    if (current + num2 > sum)
        return hasPathSumRec(node->right, sum, num);

    else
        return hasPathSumRec(node->right, sum, current);

}
else if (node->right == NULL){
    num1 = node->left->data;
    if (current + num1 > sum)
        return hasPathSumRec(node->left, sum, num);
    else
        return hasPathSumRec(node->left, sum, current);

}
else{
    num1 = node->left->data;
    num2 = node->right->data;
    /LEFT SIDE--------------------------------------------------/
    if (current + num1 > sum)
        num2 = hasPathSumRec(node->left, sum, num);
    else
        num2 = hasPathSumRec(node->left, sum, current);
    /RIGHT SIDE--------------------------------------------------/
    if (current + num2 > sum)
        num1 = hasPathSumRec(node->right, sum,num);
    else
        num1 = hasPathSumRec(node->right, sum, current);


    if (num1 > 0 || num2 > 0)
        return 1;
    else
        return 0;
}

Answer 1

正如您已经提到的，您将树值的总和计算为其子树的总和加上根值的总和。很明显，一旦您可以计算这棵树的总和，您就已经计算了其所有子树的总和。因此，剩下要做的唯一一件事就是添加一个检查，如果总和等于所需的值并返回它。在这里您可以找到这个想法的实现和 Minimal, Complete, and Verifiable example ，您应该首先提供它，从而节省人们(我)编写的精力。

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct _TNode {
    int data;
    struct _TNode *left, *right;
} TNode;

typedef struct {
    TNode *root;
} Tree;

typedef struct {
    int sum;
    bool found;
} hasPathSumRec_t;

hasPathSumRec_t hasPathSumRec(TNode* node, int sum)
{
    hasPathSumRec_t ret = { 0, false };
    if (!node)
        return ret;

    hasPathSumRec_t ret_left = hasPathSumRec(node->left, sum);
    hasPathSumRec_t ret_right = hasPathSumRec(node->right, sum);

    ret.sum = ret_left.sum + ret_right.sum + node->data;
    ret.found = ret_left.found || ret_right.found || ret.sum == sum;
    return ret;
}

int hasPathSum(Tree tr, int sum) {
    return hasPathSumRec(tr.root, sum).found;
}

int main(void)
{
    /*
    1 / 2 / 3 / *
      |   |   \ *
      |   \ 5 / * 
      |       \ *
      \ 4 / 6 / 7 / *
          |   |   \ *
          |   \ *
          \ 8 / *
              \ 9 / *
                  \ *
    */

    TNode n[] = {
        { 1, n + 4 - 1, n + 2 - 1 },
        { 2, n + 5 - 1, n + 3 - 1 },
        { 3, NULL, NULL },
        { 4, n + 8 - 1, n + 6 - 1 },
        { 5, NULL, NULL },
        { 6, NULL, n + 7 - 1 },
        { 7, NULL, NULL },
        { 8, n + 9 - 1, NULL },
        { 9, NULL, NULL },
    };

    Tree t = { n };

    int tests[] = { 8, 9, 10, 12, 13, 17 };
    size_t ntests = sizeof tests / sizeof *tests;
    for (size_t i = 0; i < ntests; ++i)
        printf("%i - %i\n", tests[i], hasPathSum(t, tests[i]));
}

如果发现或超过总和，进一步的改进可以允许提前退出。