import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;
class Ideone {
public static final int[] answer(int height, int[] nodes) {
int[] ans = new int[nodes.length];
Map
<Integer, Integer
> indices
= new HashMap
<>(); IntStream.range(0, nodes.length).forEachOrdered(i -> indices.put(nodes[i], i));
int next = postOrder(height, 0, 0, indices, ans);
if (next < 0) {
int i = indices.get(-next);
ans[i] = -1;
}
return ans;
}
private static int postOrder
(int limit,
int depth,
int next, Map
<Integer, Integer
> indices,
int[] ans
) { if (depth == limit) {
return next;
}
// left
int left = postOrder(limit, depth + 1, next, indices, ans);
next = left < 0 ? -left : left;
int right = postOrder(limit, depth + 1, next, indices, ans);
next = right < 0 ? -right : right;
int me = next + 1;
if (left < 0) {
int i = indices.get(-left);
ans[i] = me;
}
if (right < 0) {
int i = indices.get(-right);
ans[i] = me;
}
return indices.containsKey(me) ? -me : me;
}
public static void main
(String[] args
) { testRun(3, new int[] { 7, 3, 5, 1 }, new int[] { -1, 7, 6, 3 });
testRun(5, new int[] { 19, 14, 28 }, new int[] { 21, 15, 29 });
}
private static void testRun(int height, int[] input, int[] output) {
int[] ans = answer(height, input);
System.
out.
printf("Input height %d and nodes %s:\n%s\n%s\n", height,
Arrays.
toString(input
),
}
}
aW1wb3J0IGphdmEudXRpbC5BcnJheXM7CmltcG9ydCBqYXZhLnV0aWwuSGFzaE1hcDsKaW1wb3J0IGphdmEudXRpbC5NYXA7CmltcG9ydCBqYXZhLnV0aWwuc3RyZWFtLkludFN0cmVhbTsKCmNsYXNzIElkZW9uZSB7CiAgICBwdWJsaWMgc3RhdGljIGZpbmFsIGludFtdIGFuc3dlcihpbnQgaGVpZ2h0LCBpbnRbXSBub2RlcykgewogICAgICAgIGludFtdIGFucyA9IG5ldyBpbnRbbm9kZXMubGVuZ3RoXTsKICAgICAgICBNYXA8SW50ZWdlciwgSW50ZWdlcj4gaW5kaWNlcyA9IG5ldyBIYXNoTWFwPD4oKTsKICAgICAgICBJbnRTdHJlYW0ucmFuZ2UoMCwgbm9kZXMubGVuZ3RoKS5mb3JFYWNoT3JkZXJlZChpIC0+IGluZGljZXMucHV0KG5vZGVzW2ldLCBpKSk7CiAgICAgICAgaW50IG5leHQgPSBwb3N0T3JkZXIoaGVpZ2h0LCAwLCAwLCBpbmRpY2VzLCBhbnMpOwogICAgICAgIGlmIChuZXh0IDwgMCkgewogICAgICAgICAgICBpbnQgaSA9IGluZGljZXMuZ2V0KC1uZXh0KTsKICAgICAgICAgICAgYW5zW2ldID0gLTE7CiAgICAgICAgfQogICAgICAgIHJldHVybiBhbnM7CiAgICB9CgogICAgcHJpdmF0ZSBzdGF0aWMgaW50IHBvc3RPcmRlcihpbnQgbGltaXQsIGludCBkZXB0aCwgaW50IG5leHQsIE1hcDxJbnRlZ2VyLCBJbnRlZ2VyPiBpbmRpY2VzLCBpbnRbXSBhbnMpIHsKICAgICAgICBpZiAoZGVwdGggPT0gbGltaXQpIHsKICAgICAgICAgICAgcmV0dXJuIG5leHQ7CiAgICAgICAgfQogICAgICAgIC8vIGxlZnQKICAgICAgICBpbnQgbGVmdCA9IHBvc3RPcmRlcihsaW1pdCwgZGVwdGggKyAxLCBuZXh0LCBpbmRpY2VzLCBhbnMpOwogICAgICAgIG5leHQgPSBsZWZ0IDwgMCA/IC1sZWZ0IDogbGVmdDsKICAgICAgICBpbnQgcmlnaHQgPSBwb3N0T3JkZXIobGltaXQsIGRlcHRoICsgMSwgbmV4dCwgaW5kaWNlcywgYW5zKTsKICAgICAgICBuZXh0ID0gcmlnaHQgPCAwID8gLXJpZ2h0IDogcmlnaHQ7CgogICAgICAgIGludCBtZSA9IG5leHQgKyAxOwoKICAgICAgICBpZiAobGVmdCA8IDApIHsKICAgICAgICAgICAgaW50IGkgPSBpbmRpY2VzLmdldCgtbGVmdCk7CiAgICAgICAgICAgIGFuc1tpXSA9IG1lOwogICAgICAgIH0KICAgICAgICBpZiAocmlnaHQgPCAwKSB7CiAgICAgICAgICAgIGludCBpID0gaW5kaWNlcy5nZXQoLXJpZ2h0KTsKICAgICAgICAgICAgYW5zW2ldID0gbWU7CiAgICAgICAgfQoKICAgICAgICByZXR1cm4gaW5kaWNlcy5jb250YWluc0tleShtZSkgPyAtbWUgOiBtZTsKCiAgICB9CgogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgICAgIHRlc3RSdW4oMywgbmV3IGludFtdIHsgNywgMywgNSwgMSB9LCBuZXcgaW50W10geyAtMSwgNywgNiwgMyB9KTsKICAgICAgICB0ZXN0UnVuKDUsIG5ldyBpbnRbXSB7IDE5LCAxNCwgMjggfSwgbmV3IGludFtdIHsgMjEsIDE1LCAyOSB9KTsKICAgIH0KCiAgICBwcml2YXRlIHN0YXRpYyB2b2lkIHRlc3RSdW4oaW50IGhlaWdodCwgaW50W10gaW5wdXQsIGludFtdIG91dHB1dCkgewogICAgICAgIGludFtdIGFucyA9IGFuc3dlcihoZWlnaHQsIGlucHV0KTsKICAgICAgICBTeXN0ZW0ub3V0LnByaW50ZigiSW5wdXQgaGVpZ2h0ICVkIGFuZCBub2RlcyAlczpcbiVzXG4lc1xuIiwgaGVpZ2h0LCBBcnJheXMudG9TdHJpbmcoaW5wdXQpLAogICAgICAgICAgICAgICAgQXJyYXlzLnRvU3RyaW5nKGFucyksIEFycmF5cy50b1N0cmluZyhvdXRwdXQpKTsKICAgIH0KCn0K