Leetcode #106 Construct Binary Tree from Inorder and Postorder Traversal

[yokostan]

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length != postorder.length) {
            return null;
        }
        return helper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    private TreeNode helper(int[] inorder, int inS, int inE, int[] postorder, int postS, int postE) {
        if (inS > inE || postS > postE) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postE]);
        int position = findPosition(inorder, inS, inE, postorder[postE]);

        int leftSize = position - inS;
        int rightSize = inE - inS -leftSize;
        root.left = helper(inorder, inS, position - 1, postorder, postS, postE - rightSize - 1);
        root.right = helper(inorder, position + 1, inE, postorder, postE - rightSize, postE - 1);

        return root;
    }

    private int findPosition(int[] inorder, int inS, int inE, int key) {
        for (int i = inS; i <= inE; i++) {
            if (inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}

I feel so delightful to solve this problem in around 15 minutes after studying #127 ! I love Leetcode! Let's go grab some lunch! Wait... I only beat 15% in runnning time? Let's see what is happening.

If we use HashMap, our running time will be fire! Here we use HashMap to quickly get the corresponding index of each root element instead of running findPosition function, and we only recur on inorder but subtract from postIndex by 1 in each recursion.

class Solution {
     int postIndex;
    Map<Integer, Integer> map; // construct a map key-inorder element, value-element's index 
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // corner case
        if (postorder == null || inorder == null || postorder.length == 0 || inorder.length == 0) {
            return null; 
        }
        postIndex = postorder.length-1;
        map = new HashMap<Integer, Integer>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return buildTree(inorder, postorder, 0, inorder.length-1); 
    }

    private TreeNode buildTree(int[] inorder, int[] postorder, int inS, int inE) {
        if (inS == inE) {
            postIndex--;
            return new TreeNode(inorder[inS]);
        }
        else if (inS > inE) {
            return null;
        }
        int rootVal = postorder[postIndex]; 
        TreeNode root = new TreeNode(rootVal);
        postIndex--;
        // determine the subarray for left and right tree according to root's index in inorder
        int rootIndexInInorderArray = map.get(rootVal);
        root.right = buildTree(inorder, postorder, rootIndexInInorderArray+1, inE);
        root.left = buildTree(inorder, postorder, inS, rootIndexInInorderArray-1);

        return root; 
    }

}