Java O(n) time and O(n) space Solution


  • 0
    A
    public TreeNode buildTree(final int[] preOrder, final int[] inOrder) {
            Map<Integer, Integer> inOrderValueIndexMap = new HashMap<>();
            for (int i = 0; i < inOrder.length; i++) {
                inOrderValueIndexMap.put(inOrder[i], i);
            }
    
            return buildTreeHelper(inOrderValueIndexMap, preOrder, 0, preOrder.length-1, 0, inOrder.length-1);
        }
    
        private TreeNode buildTreeHelper(final Map<Integer, Integer> inOrderValueIndexMap, final int[] preOrder,
                                         final int preOrderStart, final int preOrderEnd, final int inOrderStart, final int inOrderEnd) {
            if (preOrderStart <= preOrderEnd && inOrderStart <= inOrderEnd) {
                int rootValue = preOrder[preOrderStart];
                int rootInOderIndex = inOrderValueIndexMap.get(rootValue);
                int leftSubTreeSize = rootInOderIndex - inOrderStart;
                int rightSubTreeSize = inOrderEnd - rootInOderIndex;
    
                TreeNode node = new TreeNode(rootValue);
                node.left = buildTreeHelper(inOrderValueIndexMap, preOrder,
                        preOrderStart + 1, preOrderStart + leftSubTreeSize,
                        inOrderStart, rootInOderIndex - 1);
                node.right = buildTreeHelper(inOrderValueIndexMap, preOrder,
                        preOrderEnd - rightSubTreeSize + 1, preOrderEnd,
                        rootInOderIndex + 1, inOrderEnd);
                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.