fork(8) 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 Answer {
  7.  
  8. private static final int parent(int height, int node) {
  9. int size = (int)Math.pow(2, height) - 1;
  10.  
  11. if (node == size) {
  12. return -1;
  13. }
  14.  
  15. int before = 0;
  16. do {
  17. if (size == 0) {
  18. throw new IllegalStateException();
  19. }
  20. size >>>= 1;
  21. int left = before + size;
  22. int right = left + size;
  23. int me = right + 1;
  24. if (left == node || right == node) {
  25. return me;
  26. }
  27. if (node > left) {
  28. before = left;
  29. }
  30. } while (true);
  31.  
  32. }
  33.  
  34. public static final int[] answerToo(int height, int[] nodes) {
  35. return IntStream.of(nodes).map(n -> parent(height, n)).toArray();
  36. }
  37.  
  38. public static final int[] answer(int height, int[] nodes) {
  39. int[] ans = new int[nodes.length];
  40. Map<Integer, Integer> indices = new HashMap<>();
  41. IntStream.range(0, nodes.length).forEachOrdered(i -> indices.put(nodes[i], i));
  42. int next = postOrder(height, 0, 0, indices, ans);
  43. if (next < 0) {
  44. int i = indices.get(-next);
  45. ans[i] = -1;
  46. }
  47. return ans;
  48. }
  49.  
  50. private static int postOrder(int limit, int depth, int next, Map<Integer, Integer> indices, int[] ans) {
  51. if (depth == limit) {
  52. return next;
  53. }
  54. // left
  55. int left = postOrder(limit, depth + 1, next, indices, ans);
  56. next = left < 0 ? -left : left;
  57. int right = postOrder(limit, depth + 1, next, indices, ans);
  58. next = right < 0 ? -right : right;
  59.  
  60. int me = next + 1;
  61.  
  62. if (left < 0) {
  63. int i = indices.get(-left);
  64. ans[i] = me;
  65. }
  66. if (right < 0) {
  67. int i = indices.get(-right);
  68. ans[i] = me;
  69. }
  70.  
  71. return indices.containsKey(me) ? -me : me;
  72.  
  73. }
  74.  
  75. public static void main(String[] args) {
  76. testRun(3, new int[] { 7, 3, 5, 1 }, new int[] { -1, 7, 6, 3 });
  77. testRun(5, new int[] { 19, 14, 28 }, new int[] { 21, 15, 29 });
  78. }
  79.  
  80. private static void testRun(int height, int[] input, int[] output) {
  81. int[] ans = answer(height, input);
  82. int[] ans2 = answerToo(height, input);
  83. System.out.printf("Input height %d and nodes %s:\n%s\n%s\n", height, Arrays.toString(input),
  84. Arrays.toString(ans), Arrays.toString(ans2), Arrays.toString(output));
  85. }
  86.  
  87. }
  88.  
Success #stdin #stdout 0.1s 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]