重建二叉树_JAVA_中等

• 前序遍历为{根节点，{左孩子树}，{右孩子树}}，中序遍历为{{左孩子树}，根节点，{右孩子树}}
• 可以从前序遍历拿出根节点（首位）确定中序遍历数组的根节点位置，从而划分左右子树在两序遍历数组的范围，接下来就是左右子树的构建过程，即将一个大问题分割成了相同类型但规模更小的子问题，直接递归解决。

public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        return reConstructBinaryTreeRec(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }

    public TreeNode reConstructBinaryTreeRec(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
        // 处理数组为空判断
        if(preStart > preEnd || inStart > inEnd) {
            return null;
        }

        // 找出根节点
        int rootPosition = inStart - 1;
        while(++rootPosition <= inEnd) {
            if(pre[preStart] == in[rootPosition]) {
                break;
            }
        }

        // 建立根节点并给构建左右孩子节点
        TreeNode root = new TreeNode(pre[preStart]);
        root.left = reConstructBinaryTreeRec(pre, preStart + 1, preStart + rootPosition - inStart, in, inStart, rootPosition - 1);
        root.right = reConstructBinaryTreeRec(pre, preStart + rootPosition - inStart + 1, preEnd, in, rootPosition + 1, inEnd);
        return root;
    }
}