java - 如何查找二叉树中的数字之和？

Question

我需要在二叉树中搜索任何数字组合，这将给出我正在搜索的总和。 例如，对于具有数字:9,1,6,3,2,5的树，如果系统收到的总和为18，它将返回字符串“9,1,3,5”。请问我该怎么做。

该组合需要在 Pathway 中从根开始向下，该方法需要在 BackTracking 递归中工作

我写的代码是:

public String path(int sum)
    {
        return path(sum, root);
    }
    private String path(int sum, Node t)
    {
        if (t == null)
            return "";

        sum = sum - t.getNumber();

        if (sum == 0)
            return t.getNumber() + ", ";


        return path(sum, t.getLeftSon()) + path(sum, t.getRightSon()); 

    }

Answer 1

您的递归实现确实接近您的需要，但有一些事情需要一些调整。
首先，递归实现需要两件事才能工作:

1. 基本案例，问题最终可以通过分而治之的方法达到
2. 一般案例，用于将问题分成更小的部分，直到达到所需的基本案例。
   

<小时/>

您遇到的问题是，当您递归时，您只打印使总和为零的最终节点。这是因为最后一次调用将递归回调用它的方法，其中总和大于零。

如果该树到达叶子并且未找到总和，则该子树中不存在该总和。
返回“”;

else if总和在子树中找到。
return t.getNumber() + ", ";

else我们还没有达到总和，并且还有更多的子节点。
路径(t.getleftSon()); 路径(t.getRightSon())； 返回 t.getNumber() + ", "

我还没有在 IDE 中测试过这个确切的代码，但逻辑应该是正确的