java - 查找根和 5 的倍数之间的路径

Question

我很难实现一个程序来从 b-tree root 中找到一个节点的路径，该路径是 5 的倍数。

例子：

     12
    /  \
   4    7
  /\    /\
 5  3  4 10

将其视为树。程序应该打印

12 -> 4 -> 5

12 -> 7 -> 10

编辑：

是的，我已经尝试过，以下是我正在关注的算法：我按顺序遍历并比较 5 的倍数的值。如果是，我开始在 LinkedList 中添加节点并返回该列表。但是这种方法只有在我有一个 5 的倍数时才有效。如果有更多的倍数，它就会失败。

以下是我尝试过的：

LinkedList<Integer> getPaths(Node parent, int multiple){

    if(parent == null)
        return null;

    LinkedList list = new LinkedList();
    list = getPaths(parent.getLeftChild(), 5);


    if(parent.getSID() % multiple == 0){
        list.add(parent.getSID());
        return list;
    }

    list = getPaths(parent.getRightChild(),5);

    if(list != null)
        list.add(parent.getSID());

    return list;

}

Answer 1

问题是，当你这样做时：

list = getPaths(parent.getRightChild(), 5);

您覆盖此处返回的值：

list = getPaths(parent.getLeftChild(), 5);

您可能需要LinkedList<LinkedList<Integer>>存储所有路径。

一个全局列表：

LinkedList<LinkedList<Integer>> globalList;
LinkedList<Integer> getPaths(Node parent, int multiple)

或传递列表：

LinkedList<Integer> getPaths(Node parent, int multiple,
                             LinkedList<LinkedList<Integer>> bigList)

但是，要使其正常工作将需要对您当前的程序进行相当多的更改，您需要在某些点复制列表，并且可能会切换填充列表的顺序（将其从自下而上的填充更改为顶部-向下）。