fork(6) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
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]
https://ideone.com/J0lMrf
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!