二叉树最大和

Question

问题:二叉树作为输入，二叉树的每个节点包含一个整数值。查找节点集合的最大和，以便满足以下两个条件。

• 如果节点的父节点考虑求和，则不能考虑节点。
• 如果节点的任一子节点被考虑为和，则不能考虑节点。

例如：

二叉树

             15
      20            25
   5      15      5  

我们能得到的最大和是考虑[20, 25]，即45。

为了实现这一点，我使用了O(n^2)方法，代码在这里。

我试图对其进行优化，并寻求关于改进算法、代码效率和清洁度的反馈。

tree是以BFS方式给出的树的字符串表示形式。_代替空元素。对于最深层元素的空表示，不给出_。

上面的树将表示为15 20 25 5 15 5 _

static int findMaxSum(String tree) {
    String[] tokens = tree.split(" ");
    int max = 0;
    for (int i = 0; i < tokens.length; i++) {
        if (!isValidToken(tokens[i])) {
            continue;
        }
        Set<Integer> set = new HashSet<>();
        //wildcard entry
        set.add(i);
        int sum = Integer.parseInt(tokens[i]);
        for (int j = 0; j < tokens.length; j++) {
            if (isValidToken(tokens[j])) {
                if(!set.contains(j) && !set.contains(getParentIndex(j))){
                    if (!set.contains(getLeftChildIndex(j)) && !set.contains(getRightChildIndex(j))) {
                        set.add(j);
                        sum += Integer.parseInt(tokens[j]);
                    }
                }
            }
        }
        max = Math.max(max,sum);
    }

    return max;
}


static boolean isValidToken(String token) {
    return !"_".equals(token);
}

static int getLeftChildIndex(int parentIndex) {
    return parentIndex * 2 + 1;
}

static int getRightChildIndex(int parentIndex) {
    return parentIndex * 2 + 2;
}

static int getParentIndex(int childIndex) {
    return (childIndex - 1)/2;
}

注意:此代码工作，但效率不高。我正在寻找如何改进它的想法。

Answer 1

我想我理解这个问题，如果我没有弄错的话，这意味着我们想要从树中选择一组节点，这样就不会有两个节点连接到树中。如果您只是以递归的方式来考虑这个问题，您可以选择一个节点，而不是它的两个子节点，递归地试图解决与孙辈相同的问题。或者，您不使用节点，而是取两个子节点解决的相同问题的总和。实现可以如下所示(我省略了下划线，使用索引来检查树的末尾)：

static int max(final String tree) {
    return max(0, stream(tree.split(" ")).mapToInt(Integer::parseInt).toArray());
}

static int max(final int root, final int... nodes) {
    if (root >= nodes.length) {
        return 0;
    }

    final int maxWithRoot =
            nodes[root]
            + max(getLeftChildIndex (getLeftChildIndex(root)),  nodes)
            + max(getRightChildIndex(getLeftChildIndex(root)),  nodes)
            + max(getLeftChildIndex (getRightChildIndex(root)), nodes)
            + max(getRightChildIndex(getRightChildIndex(root)), nodes);

    final int maxWithoutRoot = max(getLeftChildIndex(root),  nodes) + 
                               max(getRightChildIndex(root), nodes);

    return Integer.max(maxWithoutRoot, maxWithRoot);
}

现在还可以看到，对于同一个节点，将多次执行相同的计算。但是，由于max函数的结果仅依赖于root索引，所以可以缓存计算，这意味着您只为每个节点计算了一次结果。

在这种情况下，您可以使用节点索引作为缓存索引创建一个整数数组作为缓存。

Answer 2

如果我正确地理解了规则，就可以用O(N)以下列方式实现：

1. 向每个节点附加第二个整数
2. 非叶节点= 0，叶节点=节点的主值.
3. 先做深度第一步。
4. 对于访问所有子节点的每个节点，将第二个值设置为直接子节点的第二个值之和。如果第二个值小于主值，则将其设置为主值。

(为说明起见，我将第二个叶节从15调整为10 )

在第二步之后。

          15
           0
   20            25
    0             0
5      10      5  
5      10      5  

在第一次访问非叶之后：

          15
           0
   20            25
-> 15 <-          0
5      10  
5      10      5  

15较小，因此将其设置为20

          15
           0
   20            25
   20             0
5      10      5  
5      10      5  

最后一棵树后的算法：

          15
          45 <- answer
   20            25
   20            25
5      10      5  
5      10      5