Use DFS on the whole tree, for each subtree, save the largest three positive costs and the smallest three non-positive costs. This can be done by using two Heaps with the size of at most three.

You need to store at most six values at each subtree.

If there are more than three values in total, we can sort them. Let’s call the resultant array <code>A</code>, the maximum product of three is <code>max(A[0] * A[1] * A[n - 1], A[n - 1] * A[n - 2] * A[n - 3])</code>. Don’t forget to set the result to <code>0</code> if the value is negative.

If there are less than three values for a subtree, set its result to <code>1</code>.