[106. Construct Binary Tree from Inorder and Postorder Traversal] #leetcode

106_0827.java

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return dfs(inorder, postorder, inorder.length-1, 0, inorder.length-1);
    }
    
    private TreeNode dfs(int[] inorder, int[] postorder, int postInd, int leftIn, int rightIn) {
        if ( leftIn > rightIn || postInd < 0 ) return null;
        
        int value = postorder[postInd];
        TreeNode node = new TreeNode(value);
        
        int tmp = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == value) {
                tmp = i;
                break;
            }
        }
        
        node.right = dfs(inorder, postorder, postInd-1, tmp+1, rightIn);
        node.left = dfs(inorder, postorder, postInd-(rightIn - tmp + 1), leftIn, tmp-1);
        
        return node;
    }
}