Construct Bst Preorder-Inorder, Inorder-Postorder

leetcode 105, 106.

Given preorder and inorder traversal of a tree, construct the binary tree.

Given inorder and postorder traversal of a tree, construct the binary tree.

Solution. These two are classical tree problem in data structure class.

For preorder-inorder, the process is like below:

For inorder-postorder, the process is like below:

When we have preorder[preStart], and we want to find inMid. One technique is that we store the inorder[pos] and pos in hashmap. In this way, we can find the inMid in O(1) time.

Preorder-inorder:

public static TreeNode buildTree(int[] preorder, int[] inorder) {
    if (inorder == null) {
        return null;
    }
    HashMap<Integer, Integer> hm = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        hm.put(inorder[i], i);
    }
    return helper(inorder, preorder, 0, inorder.length - 1, 0, preorder.length - 1, hm);
}

private static TreeNode helper(int[] inorder, int[] preorder, int inStart, int inEnd, int preStart, int preEnd, HashMap<Integer, Integer> hm) {
    if (inStart > inEnd) {
        return null;
    }
    int inMid = hm.get(preorder[preStart]);
    TreeNode node = new TreeNode(inorder[inMid]);
    node.left = helper(inorder, preorder, inStart, inMid - 1, preStart + 1, preStart + inMid - inStart, hm);
    node.right = helper(inorder, preorder, inMid + 1, inEnd, preStart + inMid - inStart + 1, preEnd, hm);
    return node;
}

Inorder-postorder:

public static TreeNode buildTree(int[] inorder, int[] postorder) {
    if (inorder == null) {
        return null;
    }
    HashMap<Integer, Integer> hm = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        hm.put(inorder[0], i);
    }
    return helper(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1, hm);
}

private static TreeNode helper(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd, HashMap<Integer, Integer> hm) {
    if (inStart > inEnd) {
        return null;
    }
    int inMid = hm.get(postorder[postEnd]);
    TreeNode node = new TreeNode(inorder[inMid]);
    node.left = helper(inorder, postorder, inStart, inMid - 1, postStart, postEnd - (inEnd - inMid) - 1, hm);
    node.right = helper(inorder, postorder, inMid + 1, inEnd, postEnd - (inEnd - inMid), postEnd - 1, hm);
    return node;
}

Check my code on github: preorder-inorder, inorder-postorder.