leetcode:重建二叉树

package com.wuli.algorithm.重建二叉树;

import java.util.Arrays;

/**
 * 题目描述：
 *
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
 * 则重建二叉树并返回。
 */

public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        // 数组长度为0的时候需要处理
        if (pre.length == 0) {
            return null;
        }
        int rootValue = pre[0];

        // 数组长度为1的时候需要单独处理
        if (pre.length == 1) {
            return new TreeNode(rootValue);
        }

        // 首先找到root所在的位置 确定好中序左子树和右子树的范围
        TreeNode root = new TreeNode(rootValue);
        int rootIndex = 0;
        for (int i = 0; i < in.length; i++) {
            if (rootValue == in[i]) {
                rootIndex = i;
                break;
            }
        }
        // 递归，假设root的左子树都已经构建完毕，那么只要将左子树按到root左右即可
        // 这里注意Arrays.copyOfRange(int[],start,end)是[)的区间
        root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, rootIndex + 1),
            Arrays.copyOfRange(in, 0, rootIndex));
        root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, rootIndex + 1, pre.length),
            Arrays.copyOfRange(in, rootIndex, in.length));

        return root;

    }

    public static void main(String[] args) {
        int pre[] = {1, 2, 4, 7, 3, 5, 6, 8};
        int in[] = {4, 7, 2, 1, 5, 3, 8, 6};
        TreeNode treeNode = new Solution().reConstructBinaryTree(pre,in);
    }
}