二叉树中给定总和的路径 - 在递归中 | Java

Question

我写了一段代码，需要检查并打印二叉树是否存在从根向前的路径，如果我们对每一步中的对象求和，我们将得到给定的总和。

例如：

     1
    /  \
  4     1
 / \   / \
8   2 6   8
   / \   / \
 10   5 2   8

假设我们得到了数字 5。该程序需要在字符串“1、4”中 return - 因为它给出了总和 5.

如果给定数字 8，程序将 return 放入字符串“1, 1, 6” - 因为加在一起它给出总和 8.

那是我写的程序：

    public String sum(int x)    {
    return sum(x, root, 0, "");
}

private String sum(int x, Node tree, int num, String s) {

    if(tree == null)
        return "";

    if(num == x) {
        s=s+tree.getNumber() + ", ";
        return s;
    }

    if (num != x)

        s=s+tree.getNumber() + ", ";
        sum(x, tree.getLeftSon(), num, s);
        sum(x, tree.getRightSon(), num, s);

return s;

当我运行代码时，它看起来一切正常 - 但当它进入 "if(num == x)" 中的条件结束时 - 它只是没有 return 值！

i 运行调试器，并获得了我想要的所有正确值。如果程序 return s 的值并自行停止 - 我的程序将按我喜欢的方式运行。但它只是继续到下一个 "if" 我不知道该怎么办...

我们将竭诚为您提供帮助。

Answer 1

代码忽略了这些调用的 return 值：

    sum(x, tree.getLeftSon(), num, s);
    sum(x, tree.getRightSon(), num, s);

这可能就是您得到错误结果的原因。

行

 s=s+tree.getNumber() + ", ";

将创建一个新变量并将其分配给 "s" 但不会更改您传入的原始变量 "s"。在 Java 中您不能传递引用，因此您必须使用 return 值。

二叉树中给定总和的路径 - 在递归中 | Java

Path of given sum in Binary Tree - in Recursion | Java

java

recursion

binary-tree

backtracking