[Java] Simply traverse the tree twice
Intuition & Approach\n\nJust traverse the tree twice. First time calculate the height of subtrees, and second time calculate the max height without a node.\n\nF
# Intuition & Approach\n\nJust traverse the tree twice. First time calculate the height of subtrees, and second time calculate the max height without a node.\n\nFirst traversal is trivial.\nSecond traversal is a bit tricky. If we remove left child of root, then the possible max height of the new tree is the height of right child + 1. We can recursively get this "possible max height".\n\n# Complexity\n- Time complexity: O(n)\n\n- Space complexity: O(n)\n\n# Code\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        Map<Integer, Integer> heightsRooted = new HashMap<>();\n        getHeightRootedAt(root, heightsRooted);\n\n        int[] heightsWithout = new int[heightsRooted.size() + 1];\n        getHeightsWithoutNode(root, 0, 0, heightsWithout, heightsRooted);\n\n        int[] result = new int[queries.length];\n        for (int i = 0; i < queries.length; i++) {\n            result[i] = heightsWithout[queries[i]];\n        }\n\n        return result;\n    }\n\n    private void getHeightsWithoutNode(TreeNode node, int height, int possibleMaxHeight, int[] heightsWithout, Map<Integer, Integer> heightsRooted) {\n        if (node == null) {\n            return;\n        }\n\n        int leftHeight = node.left == null ? -1 : heightsRooted.get(node.left.val);\n        int rightHeight = node.right == null ? -1 : heightsRooted.get(node.right.val);\n\n        getHeightsWithoutNode(node.left, height + 1, Math.max(possibleMaxHeight, rightHeight + height + 1), heightsWithout, heightsRooted);\n        getHeightsWithoutNode(node.right, height + 1, Math.max(possibleMaxHeight, leftHeight + height + 1), heightsWithout, heightsRooted);\n\n        heightsWithout[node.val] = Math.max(height - 1, possibleMaxHeight);\n    }\n\n    private int getHeightRootedAt(TreeNode node, Map<Integer, Integer> heightsRooted) {\n        if (node == null) {\n            return -1;\n        }\n\n        int maxHeight = 1 + Math.max(getHeightRootedAt(node.left, heightsRooted), getHeightRootedAt(node.right, heightsRooted));\n        heightsRooted.put(node.val, maxHeight);\n        return maxHeight;\n    }\n}\n```
['Java']