c - 根到叶路径总和 = 给定数

Question

这个递归是如何进行的？这是第一次 14-10=4 并且 if (node->left) 条件满足 so 函数 with node->left(node 8) 和 sum value(4) 被调用，但是 node->left 和 node->right 中的 or 条件有什么用？

假设给定的总和是 21 然后在我们向下递归最终节点 3 并且在 node->left 函数中调用 sum=3 时，1 返回为 sum=0 并且没有子节点但是 1 返回哪里是节点 8 之后我们去节点 5 吗？

如果我们这样做，节点 5 不返回任何值，那么它如何计算返回 1 的左子节点和不返回任何值的右子节点？我没有看到实际使用 or 条件的地方，为什么有必要在 node->left 和 node->right if 条件中使用它？

int main()
{
  int sum=14; //sum=21;

  struct node *root = newnode(10);
  root->left        = newnode(8);
  root->right       = newnode(2);
  root->left->left  = newnode(3);
  root->left->right = newnode(5);
  root->right->left = newnode(2);

  if(hasPathSum(root, sum))
   printf("There is a root-to-leaf path with sum %d", sum);
  else
   printf("There is no root-to-leaf path with sum %d", sum);

   getchar();
   return 0;
}

bool hasPathSum(struct node* node, int sum)
 {
  /* return true if we run out of tree and sum==0 */
   if (node == NULL)
   {
      return (sum == 0);
   }

   else
  {
    bool ans = 0;     
    int subSum = sum - node->data;

    if ( subSum == 0 && node->left == NULL && node->right == NULL )
     return 1;

    if(node->left)
    ans = ans || hasPathSum(node->left, subSum);
    if(node->right)
    ans = ans || hasPathSum(node->right, subSum);

    return ans;
    }
}

Answer 1

在:

if(node->left)
    ans = ans || hasPathSum(node->left, subSum);
if(node->right)
    ans = ans || hasPathSum(node->right, subSum);

第一个“ans = ans || ...”没有任何功能，因为 ans 是假的。在第二个 if 中，ans 可能已被第一个 if 设置为 true，然后 hasPathSum 将不会被调用。但是，它具有良好的正交外观和易于阅读的代码