(分治算法4) leecode 105 从前序与中序遍历构建二叉树

题目描述

给定两个整数数组preorder和inorder，其中preorder是二叉树的先序遍历，inorder是同一棵树的中序遍历，请构造二叉树并且返回其根节点。

分治算法求解

前序遍历的第一个就是根节点，根据根节点的位置，我们可以在中序遍历中知道这棵树的左子树和右子树。
然后从子树中，前序遍历的第一个元素就是左子树的根节点，这样的话我们就可以利用分治算法来构建二叉树。

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 || inorder.length == 0){
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        for(int i =0 ; i < preorder.length; i++){
        //这句话就是找到子树的根
            if(preorder[0] == inorder[i]){
                root.left = buildTree(Arrays.copyOfRange(preorder,1,i+1),Arrays.copyOfRange(inorder,0,i));
                root.right = buildTree(Arrays.copyOfRange(preorder,i+1,preorder.length), Arrays.copyOfRange(inorder,i+1,inorder.length));
                break;
            }
        }
        return root;
    }
}