如何在二叉树中搜索数字之和？

Question

我需要在 BinaryTree 中搜索任何数字组合，以得到我要搜索的总和。例如，对于具有以下数字的树：9,1,6,3,2,5 如果系统将收到 18 的总和，它将 return 字符串“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

您的递归实现确实接近您的需要，但有些地方需要调整。
首先，递归实现需要两件事才能起作用：

Base Case 问题最终可以通过分而治之的方法达到
一般情况，用于将问题分成更小的部分，直到达到所需的基本情况。

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

如果那棵树到达了一个叶子并且没有找到总和，那么它不存在于那个子树中。
return "";

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

else我们还没有求和，还有更多的子节点。
path(t.getleftSon()); path(t.getRightSon()); return t.getNumber() + ", "

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

如何在二叉树中搜索数字之和？

how to search sum of numbers in Binary Tree?

java

binary-tree