剑指offer005 重建二叉树

Problem:

根据二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

Intuition:

前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果。然后分别对左右子树递归地求解。
每次递归就相当于在前序数组和中序数组中分别划一刀。首先我们根据root（前序数组的第一个元素）在中序数组中的位置对中序数组划一刀，这样这道划痕的左边部分就是左子树的中序遍历数组，划痕的右边就是右子树的中序遍历数组。然后我们记下左子树的大小，再对前序遍历的数组划一刀，这样就完成了这道题的递归过程。
我们这一题应该抓住的核心是前序遍历数组的第一个元素是root,然后该元素在中序遍历数组中的位置的左边即为左子树的元素，右边即为右子树的元素。

Solution:

 import java.util.Arrays;

public class CodingInterview_005 {

   class TreeNode{
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode(int val){
           this.val=val;
       }
   }

   

    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        // 在中序中找到前序的根
        for (int i = 0; i < in.length; i++) {
            if (in[i] == pre[0]) {
                // 左子树，注意 copyOfRange 函数，左闭右开
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                // 右子树，注意 copyOfRange 函数，左闭右开
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
                break;
            }
        }
        return root;
    }


}