105.从前序与中序遍历序列构造二叉树

题目:

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

思路:

递归:
先序第一个结点是头结点,用此分割中序为左右两个部分,为两个左右子树的中序遍历结果,同时我们就确定了左右子树的长度,以此来去先序集合划分左右子树先序遍历结果

代码:

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,len=inorder.length; i <len ; i++) {
            if (root.val==inorder[i]){
                int[] inorderLeft=Arrays.copyOfRange(inorder,0,i);
                int[] preorderLeft= Arrays.copyOfRange(preorder,1,1+inorderLeft.length);
                root.left=buildTree(preorderLeft,inorderLeft);

                int[] inorderRight=Arrays.copyOfRange(inorder,i+1,inorder.length);
                int[] preorderRight=Arrays.copyOfRange(preorder,1+inorderLeft.length,preorder.length);
                root.right=buildTree(preorderRight,inorderRight);
                break;
            }
        }
        return root;
    }