java - 如何构建具有 O(n) 空间复杂度的树？

Question

问题

给定一组整数，找到总和为 100,000,000 的这些整数的子集。

解决方案

我正在尝试构建一棵树，其中包含给定集合的所有组合以及总和。例如，如果给定的集合看起来像 0,1,2，我将构建以下树，检查每个节点的总和:

                    {}
        {}                      {0}
  {}         {1}         {0}          {0,1}
{}  {2}  {1}   {1,2}  {0}   {2}   {0,1}   {0,1,2}

由于我保留了每个节点的整数数组和总和，我应该只需要内存中树的底部(当前)级别。

问题

我当前的实现将在内存中维护整个树，因此使用了过多的堆空间。

如何更改我当前的实现，以便 GC 处理我的上层树级别？

(目前我只是在找到目标总和时抛出 RuntimeException，但这显然只是为了玩玩)

public class RecursiveSolver {
    static final int target = 100000000;
    static final int[] set = new int[]{98374328, 234234123, 2341234, 123412344, etc...};

    Tree initTree() {
        return nextLevel(new Tree(null), 0);
    }

    Tree nextLevel(Tree currentLocation, int current) {
        if (current == set.length) { return null; }
        else if (currentLocation.sum == target) throw new RuntimeException(currentLocation.getText());
        else {
            currentLocation.left = nextLevel(currentLocation.copy(), current + 1);
            Tree right = currentLocation.copy();
            right.value = add(currentLocation.value, set[current]);
            right.sum = currentLocation.sum + set[current];
            currentLocation.right = nextLevel(right, current + 1);
            return currentLocation;
        }
    }

    int[] add(int[] array, int digit) {
        if (array == null) {
            return new int[]{digit};
        }
        int[] newValue = new int[array.length + 1];
        for (int i = 0; i < array.length; i++) {
            newValue[i] = array[i];
        }
        newValue[array.length] = digit;
        return newValue;
    }

    public static void main(String[] args) {
        RecursiveSolver rs = new RecursiveSolver();
        Tree subsetTree = rs.initTree();
    }
}

class Tree {
    Tree left;
    Tree right;
    int[] value;
    int sum;

    Tree(int[] value) {
        left = null;
        right = null;
        sum = 0;
        this.value = value;
        if (value != null) {
            for (int i = 0; i < value.length; i++) sum += value[i];
        }
    }

    Tree copy() {
        return new Tree(this.value);
    }
}

Answer 1

在这里 build 树所需的时间和空间完全没有。

原因是，如果给你

• 树的一个节点
• 节点的深度
• 有序的输入元素数组

您可以使用 O(1) 操作简单地计算它的父节点、左子节点和右子节点。当您遍历树时，您可以访问所有这些内容，因此您不需要任何其他内容。