[数据结构与算法]【剑指Offer07】重建二叉树

重建二叉树
题目：输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
方法一：递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0) return null;
        TreeNode root = new TreeNode(preorder[0]);
        if(preorder.length == 1) return root;
        int tag = 0;
        for(int i = 0; i < inorder.length; i++){
            if(inorder[i] == root.val){
                tag = i;
                break;
            }
        }
        if(tag != 0){
            int[] preleft = Arrays.copyOfRange(preorder,1,tag+1);
            int[] inleft = Arrays.copyOfRange(inorder,0,tag);
            root.left = buildTree(preleft,inleft);
        }
        if(tag<inorder.length){
            int[] preright = Arrays.copyOfRange(preorder,tag+1,preorder.length);
            int[] inright = Arrays.copyOfRange(inorder,tag + 1,preorder.length);
            root.right = buildTree(preright,inright);
        }
        return root;
    }
}

方法二：迭代