Java O(n) time O(n) space


  • 0
    A
    public TreeNode buildTree(final int[] inOrder, final int[] postOrder) {
            Map<Integer, Integer> inOrderValueIndexMap = new HashMap<>();
            for (int i = 0; i < inOrder.length; i++) {
                inOrderValueIndexMap.put(inOrder[i], i);
            }
    
            return buildTreeHelper(inOrderValueIndexMap, postOrder, 0, inOrder.length - 1, 0, postOrder.length - 1);
        }
    
        private TreeNode buildTreeHelper(final Map<Integer, Integer> inorderValueIndexMap, final int[] postOrder,
                                         final int inOrderStart, final int inOrderEnd, final int postOrderStart, final int postOrderEnd) {
            if (inOrderStart <= inOrderEnd && postOrderStart <= postOrderEnd) {
                int rootValue = postOrder[postOrderEnd];
                int rootInOrderIndex = inorderValueIndexMap.get(rootValue);
                int leftSubTreeSize = rootInOrderIndex - inOrderStart;
                int rightSubTreeSize = inOrderEnd - rootInOrderIndex;
    
                TreeNode node = new TreeNode(rootValue);
                node.left = buildTreeHelper(inorderValueIndexMap, postOrder,
                        inOrderStart, inOrderStart + leftSubTreeSize - 1,
                        postOrderStart, postOrderStart + leftSubTreeSize - 1);
                node.right = buildTreeHelper(inorderValueIndexMap, postOrder,
                        rootInOrderIndex + 1, inOrderEnd,
                        postOrderEnd - rightSubTreeSize, postOrderEnd - 1);
                return node;
            } else {
                return null;
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.