[105. Construct Binary Tree from Preorder and Inorder Traversal] #lc_105

105_0812.java

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return dfs(preorder, inorder, 0, 0, preorder.length);
    }
    
    private TreeNode dfs(int[] preorder, int[] inorder, int preStart, int inStart, int inEnd) {
        if (inStart > inEnd || preStart >= preorder.length) return null;

        TreeNode node = new TreeNode(preorder[preStart]);
        
        Integer idx = 0;
        while (inorder[idx] != preorder[preStart]) {
            idx++;
        }
        node.left = dfs(preorder, inorder, preStart+1, inStart, idx-1);
        node.right = dfs(preorder, inorder, preStart+idx-inStart+1, idx+1, inEnd);
        return node;
    }
}