/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
 
 
        return buildTree(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }
 
 
    public TreeNode buildTree(int[] preorder, int prS, int prE, int[] inorder, int inS, int inE) {
 
        if (inS > inE)
            return null;
 
        int rootVal = preorder[prS];
 
        int rootIdx = -1;
 
        for (int i = inS; i <= inE; i++) {
 
            if (inorder[i] == rootVal) {
 
                rootIdx = i;
                break;
            }
        }
 
 
        TreeNode root = new TreeNode(rootVal);
 
 
        int inLS = inS;
        int inLE = rootIdx - 1;
 
        int prLS = prS + 1;
        int prLE = (inLE - inLS + prLS);
 
        int prRS = prLE + 1;
        int prRE = prE;
 
        int inRS = rootIdx + 1;
        int inRE = inE;
 
 
        root.left = buildTree(preorder, prLS, prLE, inorder, inLS, inLE);
        root.right = buildTree(preorder, prRS, prRE, inorder, inRS, inRE);
 
        return root;
    }
}

LyoqCiAqIERlZmluaXRpb24gZm9yIGEgYmluYXJ5IHRyZWUgbm9kZS4KICogcHVibGljIGNsYXNzIFRyZWVOb2RlIHsKICogICAgIGludCB2YWw7CiAqICAgICBUcmVlTm9kZSBsZWZ0OwogKiAgICAgVHJlZU5vZGUgcmlnaHQ7CiAqICAgICBUcmVlTm9kZSgpIHt9CiAqICAgICBUcmVlTm9kZShpbnQgdmFsKSB7IHRoaXMudmFsID0gdmFsOyB9CiAqICAgICBUcmVlTm9kZShpbnQgdmFsLCBUcmVlTm9kZSBsZWZ0LCBUcmVlTm9kZSByaWdodCkgewogKiAgICAgICAgIHRoaXMudmFsID0gdmFsOwogKiAgICAgICAgIHRoaXMubGVmdCA9IGxlZnQ7CiAqICAgICAgICAgdGhpcy5yaWdodCA9IHJpZ2h0OwogKiAgICAgfQogKiB9CiAqLwpjbGFzcyBTb2x1dGlvbiB7CiAgICBwdWJsaWMgVHJlZU5vZGUgYnVpbGRUcmVlKGludFtdIHByZW9yZGVyLCBpbnRbXSBpbm9yZGVyKSB7CiAgICAgICAgCiAgICAgICAgCiAgICAgICAgcmV0dXJuIGJ1aWxkVHJlZShwcmVvcmRlciwgMCwgcHJlb3JkZXIubGVuZ3RoLTEsIGlub3JkZXIsIDAsIGlub3JkZXIubGVuZ3RoLTEpOwogICAgfQogICAgCiAgICAKICAgIHB1YmxpYyBUcmVlTm9kZSBidWlsZFRyZWUoaW50W10gcHJlb3JkZXIsIGludCBwclMsIGludCBwckUsIGludFtdIGlub3JkZXIsIGludCBpblMsIGludCBpbkUpIHsKICAgICAgICAKICAgICAgICBpZiAoaW5TID4gaW5FKQogICAgICAgICAgICByZXR1cm4gbnVsbDsKICAgICAgICAKICAgICAgICBpbnQgcm9vdFZhbCA9IHByZW9yZGVyW3ByU107CiAgICAgICAgCiAgICAgICAgaW50IHJvb3RJZHggPSAtMTsKICAgICAgICAKICAgICAgICBmb3IgKGludCBpID0gaW5TOyBpIDw9IGluRTsgaSsrKSB7CiAgICAgICAgICAgIAogICAgICAgICAgICBpZiAoaW5vcmRlcltpXSA9PSByb290VmFsKSB7CiAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgIHJvb3RJZHggPSBpOwogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgCiAgICAgICAgCiAgICAgICAgVHJlZU5vZGUgcm9vdCA9IG5ldyBUcmVlTm9kZShyb290VmFsKTsKICAgICAgICAKICAgICAgICAKICAgICAgICBpbnQgaW5MUyA9IGluUzsKICAgICAgICBpbnQgaW5MRSA9IHJvb3RJZHggLSAxOwogICAgICAgIAogICAgICAgIGludCBwckxTID0gcHJTICsgMTsKICAgICAgICBpbnQgcHJMRSA9IChpbkxFIC0gaW5MUyArIHByTFMpOwogICAgICAgIAogICAgICAgIGludCBwclJTID0gcHJMRSArIDE7CiAgICAgICAgaW50IHByUkUgPSBwckU7CiAgICAgICAgCiAgICAgICAgaW50IGluUlMgPSByb290SWR4ICsgMTsKICAgICAgICBpbnQgaW5SRSA9IGluRTsKICAgICAgICAKICAgICAgICAKICAgICAgICByb290LmxlZnQgPSBidWlsZFRyZWUocHJlb3JkZXIsIHByTFMsIHByTEUsIGlub3JkZXIsIGluTFMsIGluTEUpOwogICAgICAgIHJvb3QucmlnaHQgPSBidWlsZFRyZWUocHJlb3JkZXIsIHByUlMsIHByUkUsIGlub3JkZXIsIGluUlMsIGluUkUpOwogICAgICAgIAogICAgICAgIHJldHVybiByb290OwogICAgfQp9