[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal.java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) {
            return null;
        }
        return buildSubTree(preorder, 0, preorder.length - 1, inorder, 0 , inorder.length - 1);
    }
    
    private TreeNode buildSubTree(
            int[] preorder, int preorderBegin, int preorderEnd,
            int[] inorder, int inorderBegin, int inorderEnd) {
        if (preorderBegin == preorderEnd) {
            return new TreeNode(preorder[preorderBegin]);
        } else {
            int middle = preorder[preorderBegin];
            TreeNode middleNode = new TreeNode(middle);
            int middleIndex = inorderBegin;
            for (; middleIndex <= inorderEnd; middleIndex ++) {
                if (inorder[middleIndex] == middle) {
                    break;
                }
            }
            int leftSize = middleIndex - inorderBegin;
            int rightSize = inorderEnd - middleIndex;
            if (leftSize != 0) {
                middleNode.left = buildSubTree(
                    preorder, preorderBegin + 1, preorderBegin + leftSize, inorder, inorderBegin, middleIndex - 1);
            }
            if (rightSize != 0) {
                middleNode.right = buildSubTree(
                    preorder, preorderBegin + 1 + leftSize, preorderEnd, inorder, middleIndex + 1, inorderEnd);
            }
            return middleNode;
        }
    }
}