CareerCup

I am thinking of this way:

1. we need to go from "start" to "end", then we have to cover a base distance = sum(x_i), which is go directly from start -> d_1 to d_n -> end.

2. the different patterns can be split into pieces like d_i to d_j, which means you can go back and forth between d_i and d_j as many times as you want, as long as the total distance does not exceed Z.

3. So the value P = Z - sum(x_i) can be regarded as the total distance used to go back-and-forth in any pair (d_i, d_j). Each time you made a back-and-forth between (d_i, d_j), it cost 2*x_i.

4. Then you can use DP to calculate the combinations of using x_i to make up the sum equals to P. Each x_i can be used for multiple time. Then final combinations is the total number of patterns.

5. If you need to print all the patterns, you need to search, but in a memoization way. The worst case time complexity could be O(n*P).

Does it make sense??

This solution is a good one, but it cost extra O(n) space. Is there any solution for O(1) extra space?

@kurskk141, this solution is still not perfect, we still need to figure out the min 3 negative. So the solution must be in max 3 positive, max 3 negative and min 3 negative. Of course the length of the array should be larger than 9.

I don't think "the largest 3 numbers" is the right solution, the numbers may be negative, right? two negative numbers' product is still positive. Look at the following example:
6 3 2 -100 -101
The first 3 number is 6 3 2, the product = 36. But the largest product here should be 6 * -100 * -101.

void postOrderTraversalIterative(BinaryTree *root) {
  if (!root) return;
  stack<BinaryTree*> s;
  s.push(root);
  BinaryTree *prev = NULL;
  while (!s.empty()) {
    BinaryTree *curr = s.top();
    // we are traversing down the tree
    if (!prev || prev->left == curr || prev->right == curr) {
      if (curr->left) {
        s.push(curr->left);
      } else if (curr->right) {
        s.push(curr->right);
      } else {
        cout << curr->data << " ";
        s.pop();
      }
    }
    // we are traversing up the tree from the left
    else if (curr->left == prev) {
      if (curr->right) {
        s.push(curr->right);
      } else {
        cout << curr->data << " ";
        s.pop();
      }
    }
    // we are traversing up the tree from the right
    else if (curr->right == prev) {
      cout << curr->data << " ";
      s.pop();
    }
    prev = curr;  // record previously traversed node
  }
}

This solve in O(n) time and O(h) space, where h is the depth of the tree.