[java] Preorder + Level order to build look up cache
\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n
```\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\nclass Solution {\n    public int[] treeQueries(TreeNode root, int[] queries) {\n        HashMap<Integer, Integer> nodeToHeight = new HashMap<Integer, Integer>();\n        dfsPopulate(root, nodeToHeight);\n        \n        HashMap<Integer, Integer> nodeToLevel = new HashMap<Integer, Integer>();\n        // level to nodeIds sorted by subHeights\n        HashMap<Integer, List<Integer>> levelToNodeIds = new HashMap<Integer, List<Integer>>();\n        // populate those caches through level order traverse.\n        int level = 0;\n        Deque<TreeNode> queue = new LinkedList<TreeNode>();\n        queue.offer(root);\n        while(queue.size() > 0) {\n            ++level;\n            int size = queue.size();\n            List<Integer> nodeIdsAtCurLevel = new ArrayList<Integer>();\n            for(int i = 0; i < size; ++i) {\n                TreeNode cur = queue.poll();\n                if(cur.left != null) {\n                    nodeIdsAtCurLevel.add(cur.left.val);\n                    nodeToLevel.put(cur.left.val, level);\n                    queue.offer(cur.left);\n                }\n                if(cur.right != null) {\n                    nodeIdsAtCurLevel.add(cur.right.val);\n                    nodeToLevel.put(cur.right.val, level);\n                    queue.offer(cur.right);\n                }\n            }\n            \n            nodeIdsAtCurLevel = sort(nodeIdsAtCurLevel, nodeToHeight);\n            levelToNodeIds.put(level, nodeIdsAtCurLevel);\n        }\n        \n        int[] res = new int[queries.length];\n        for(int i = 0; i < queries.length; ++i) {\n            Integer curLevel = nodeToLevel.get(queries[i]);\n            List<Integer> nodeIds = levelToNodeIds.get(curLevel);\n            int additionalHeight = 0;\n            for(Integer nodeId : nodeIds) {\n                if(nodeId != queries[i]) {\n                    additionalHeight = nodeToHeight.get(nodeId);\n\t\t\t\t\t// no longer need to iterate all list since this is in revere order by sub-height.\n                    break;\n                }\n            }\n            \n            res[i] = additionalHeight + curLevel - 1;\n        }\n        \n        return res;\n    }\n    \n    private List<Integer> sort(List<Integer>nodeIdsAtCurLevel, HashMap<Integer, Integer>nodeToHeight) {\n        Collections.sort(nodeIdsAtCurLevel, new Comparator<Integer>() {\n            @Override\n            public int compare(Integer i1, Integer i2) {\n                return nodeToHeight.get(i2) - nodeToHeight.get(i1);\n            }\n        });\n            \n        return nodeIdsAtCurLevel;\n    }\n    \n    \n    \n    private int dfsPopulate(TreeNode root, HashMap<Integer, Integer> nodeToHeight) {\n        if(root == null) {\n            return 0;\n        }\n        \n        int left = dfsPopulate(root.left, nodeToHeight);\n        int right = dfsPopulate(root.right, nodeToHeight);\n        int height = 1 + Math.max(left, right);\n        nodeToHeight.put(root.val, height);\n        return height;\n    }\n}\n```
[]