Binary Tree max sum conditionally
I think I understand the problem, which if I am not mistaken means we want to pick a set of nodes from the tree such that no two taken nodes are connected in the tree. If you just think about it in a recursive manner, you either take a node and neither of its children, recursively trying to solve the same problem with the grandchildren. Or you do not take the node, and take the sum of the same problem solved for both children. An implementation could look like this (I left out underscore, using the index to check for the end of the tree):

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 &gt;= 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);
}


You can now also see that the same calculation will be executed multiple times for the same node. But because the result of the max function only depends on the root index, you can cache the calculations, meaning you calculate the result for each node only once.

In this case, you could simply create an integer array as a cache, using the node index as the cache index.