Construct Binary Tree from Preorder and Inorder Traversal

题目
Given preorder and inorder traversal of a tree, construct the binary tree.

答案

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, 0, preorder.length - 1, 0, preorder.length - 1);
    }
    public TreeNode build(int[] preorder, int[] inorder, int pl, int pr, int il, int ir) {
        if(pl > pr) return null;
        // First, take preorder[pl] as root
        TreeNode root = new TreeNode(preorder[pl]);
        
        // Second, find root in array inorder
        int root_idx = il;
        for(int i = il; i <= ir; i++) {
            if(inorder[i] == root.val) root_idx = i;
        }
        int left_size = root_idx - il;
        int right_size = ir - root_idx;
        // Third, build subrees
        root.left = build(preorder, inorder, pl + 1, pl + left_size, il, root_idx - 1);
        root.right = build(preorder, inorder, pl + left_size + 1, pl + left_size + right_size, root_idx + 1, ir);
        return root;
    }   
}