fork(4) download
  1. import java.util.Arrays;
  2. import java.util.HashMap;
  3. import java.util.Map;
  4. import java.util.stream.IntStream;
  5.  
  6. class Ideone {
  7. public static final int[] answer(int height, int[] nodes) {
  8. int[] ans = new int[nodes.length];
  9. Map<Integer, Integer> indices = new HashMap<>();
  10. IntStream.range(0, nodes.length).forEachOrdered(i -> indices.put(nodes[i], i));
  11. int next = postOrder(height, 0, 0, indices, ans);
  12. if (next < 0) {
  13. int i = indices.get(-next);
  14. ans[i] = -1;
  15. }
  16. return ans;
  17. }
  18.  
  19. private static int postOrder(int limit, int depth, int next, Map<Integer, Integer> indices, int[] ans) {
  20. if (depth == limit) {
  21. return next;
  22. }
  23. // left
  24. int left = postOrder(limit, depth + 1, next, indices, ans);
  25. next = left < 0 ? -left : left;
  26. int right = postOrder(limit, depth + 1, next, indices, ans);
  27. next = right < 0 ? -right : right;
  28.  
  29. int me = next + 1;
  30.  
  31. if (left < 0) {
  32. int i = indices.get(-left);
  33. ans[i] = me;
  34. }
  35. if (right < 0) {
  36. int i = indices.get(-right);
  37. ans[i] = me;
  38. }
  39.  
  40. return indices.containsKey(me) ? -me : me;
  41.  
  42. }
  43.  
  44. public static void main(String[] args) {
  45. testRun(3, new int[] { 7, 3, 5, 1 }, new int[] { -1, 7, 6, 3 });
  46. testRun(5, new int[] { 19, 14, 28 }, new int[] { 21, 15, 29 });
  47. }
  48.  
  49. private static void testRun(int height, int[] input, int[] output) {
  50. int[] ans = answer(height, input);
  51. System.out.printf("Input height %d and nodes %s:\n%s\n%s\n", height, Arrays.toString(input),
  52. Arrays.toString(ans), Arrays.toString(output));
  53. }
  54.  
  55. }
  56.  
Success #stdin #stdout 0.09s 711680KB
stdin
Standard input is empty
stdout
Input height 3 and nodes [7, 3, 5, 1]:
[-1, 7, 6, 3]
[-1, 7, 6, 3]
Input height 5 and nodes [19, 14, 28]:
[21, 15, 29]
[21, 15, 29]