Recursive Binary Solution - Construct Binary Tree from Inorder and Postorder Traversal

The idea is to use the 'last' element in the postorder as the root, and find the position of cur root in InOrder, then cur root.left = recursive call with start/end position, cur root.right = recursive all with second start/end position.

Must make a decision… be alert! if iteration is kind of messy, do recursive/DP


/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder == null || postorder == null || inorder.length != postorder.length || inorder.length == 0){
            return null;
        }
        if(inorder.length == 1){
            return new TreeNode(inorder[0]);
        }
       
        return buildTreeOps(inorder, postorder, 0, inorder.length - 1, 0 , postorder.length - 1);
    }
   
    private TreeNode buildTreeOps(int[] inorder, int[] postorder, int inS, int inE, int postS, int postE){
        if(inS < 0 || postS < 0 || inS > inE || postS > postE || (inE - inS) != (postE - postS)){
            return null;
        }
        if(inS == inE && postS == postE){
            return new TreeNode(inorder[inS]);
        }
        TreeNode node = new TreeNode(postorder[postE]);
        int count = 0;
        for(int i = 0; i <= (inE - inS); i++){
            if(inorder[i + inS] == postorder[postE]){
                count = i;
            }
        }
        node.left = buildTreeOps(inorder, postorder, inS, inS + count - 1, postS, postS + count - 1);
        node.right = buildTreeOps(inorder, postorder, inS + count + 1, inE, postS + count, postE - 1);
        return node;
    }
}