0

This is the problem statement:

"Given a tree and a sum, return true if there is a path from the root down to a leaf, such that adding up all the values along the path equals the given sum."

I implemented it like this:

int hasPathSum(Node* node, int sum) {
    if(node == NULL)
        return sum == 0;

    int diff = sum - node->data;

    if(diff < 0) return 0;

    if(diff == 0)
        return node->left == NULL && node->right == NULL ? 1 : 0;

    if(diff < node->data)
        return hasPathSum(node->left, diff);
    else
        return hasPathSum(node->right, diff);
}

I only traverse 1 sub-tree and not both, depending on the difference of (sum - node->data).

However, the recommended solution required traversing both the subtrees like this:

int hasPathSum(Node* node, int sum) { 
  // return true if we run out of tree and sum==0 
  if (node == NULL) { 
    return(sum == 0); 
  } 
  else { 
  // otherwise check both subtrees 
    int subSum = sum - node->data; 
    return(hasPathSum(node->left, subSum) || 
           hasPathSum(node->right, subSum)); 
  } 
}

I don't see why do we have to traverse both the subtrees ?

Here is the source of the problem: Problem 7

EDIT:

Bad assumption on my part that the tree is a BST. Its just a binary tree.

However, if it were a BST, I'd like to hear some feedback on my implementation ? Would it not be better to do it the way I did it than the other solution ? (which is a little unfair to compare since that solution is for any binary tree)

EDIT solution:

Please see anatolyg's response here which explains the problem with my proposed solution. Thanks anatolyg.

4

4 回答 4

2

你的问题陈述没有提到任何关于树的排列方式，所以我不明白你的左/右测试试图做什么。node->left如果不对其进行测试，您将无法了解有关或node->right子树的内容。

此外，在建议的解决方案中，||如果左子树匹配，则会短路，因此您不一定要遍历两个子树。如果没有路径，您只会遍历整个树：您显然必须测试每条路径以确保没有路径。（好吧，如果你在最终路径上找到匹配项，你也会遍历整个树......）

于 2012-08-14T18:52:04.877 回答
2

二叉搜索树中节点的特殊排列仅有助于搜索数字，而不是求和。想象一棵非常大的树，深度约为 100，沿着所有左侧节点寻找路径，目标总和适中（例如 1+2+3+...+100）。

当你的算法从根开始时，diff它会很大，它会转到树的右分支，总和不一定存在（例如，所有元素都大于 1000000000，所以太大了）。

于 2012-08-14T19:01:48.720 回答
1

考虑一棵二叉树，其根节点的数据为 1。根节点有两个子树，左侧为 2，右侧为 3。节点 2 的左子树为 5。

如果你问从整个根到叶节点的路径加起来是否可以达到 8，答案是肯定的。

总根 = 1，左子树 = 2，左子树 = 5，加起来为 8。但是，您提前不知道哪条路径加起来是正确的总和（如果有的话），因此您必须沿着两个子树递归地。

二叉树代码应该很短。使用二叉树的递归性质以及树为空或具有左右子树的事实。

于 2012-08-14T19:03:13.000 回答
0

这棵树不是搜索树，因此，您从父亲的数据中对孩子的数据一无所知。

于 2012-08-14T18:53:31.167 回答