Java solution beats 80%


  • 0
    L

    A few hints while solving this problem:

    1. The question clearly says all values are unique. It means that rather than searching in O(n), use a hashmap.
    2. When you are given both inorder and postorder traversals, you would need to trim down both values for left and right side of the tree. Example is :

    Inorder: "5346"
    PostOrder: "5463"

    We will use the following algorithm:
    a. The post order contains the root at the end so start with the end and consider that the root of the tree.
    b. Find the index of that root in the inorder and now the problem divides the left part of the inorder and the right part of the inorder into two different problems. Essentially, "5" should construct the left subtree and "46" should construct the right subtree.

    The tricky part is to divide the postorder traversal string to take into account left and right subtree. You would notice that the index of the root can also act as a divided in the post order string. The postorder string contains "XYroot_val" as integer values. So Y is the length of rightside children from inorder and X is the length of leftside children from the inorder. With this information, one can write the code.

    public TreeNode buildTree(int[] inorder, int[] postorder) {
            if(inorder.length==0 || postorder.length!=inorder.length) {
                return null;
            }
            //unique elements so use map to faster lookup.
            Map<Integer,Integer> val2Idx = new HashMap<>();
            for(int i=0;i<inorder.length;i++) {
                val2Idx.put(inorder[i],i);
            }
            
            return helper(0, inorder.length-1, inorder,postorder.length-1, 0 ,postorder,val2Idx);
        }
        private TreeNode helper(int iStart, int iEnd,int[] inorder, int pStart, int pEnd ,int[] postorder,
        Map<Integer,Integer> val2Idx) {
            if(iStart>iEnd || pStart<pEnd) {
                return null;
            }
            
                //get the root.
            int val = postorder[pStart];
            int idxOfRoot = val2Idx.get(val);
            TreeNode root = new TreeNode(val);
            root.left = helper(iStart, idxOfRoot - 1, inorder,
                pStart - (iEnd - idxOfRoot + 1), pEnd, postorder, val2Idx);
            root.right = helper(idxOfRoot + 1, iEnd, inorder, pStart - 1,
                pStart - (iEnd - idxOfRoot), postorder, val2Idx);
            return root;
        }
    

Log in to reply
 

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