题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入的前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出下图所示的二叉树并输出它的头结点。

image.png

class Solution {
    func rebuildTree(_ preOrder: [Int],_ inOrder: [Int]) -> TreeNode? {
        var p = preOrder
        var i = inOrder
        return recursive(&p, 0, p.count-1, &i, 0, i.count-1)
    }
   
    //不改变原输入
    func recursive(_ preOrder: inout [Int],_ startPre: Int,_ endPre: Int,_ inOrder: inout [Int],_ startIn: Int,_ endIn: Int) -> TreeNode? {
        if startPre > endPre || startIn > endIn {
            return nil
        }
        var root  = TreeNode(preOrder[startPre])
        for index in startIn...endIn {
            if inOrder[index] == root.val {
                root.left = recursive(&preOrder, startPre+1, startPre+(index-startIn), &inOrder, startIn, index-1))
                root.right = recursive(&preOrder, startPre+(index-startIn)+1, &inOrder, index+1, endIn)
                 break
            }
        }
        return root
    }

     //改变原输入，难度低一点
    func recursive(_ preOrder: inout [Int],_ inOrder: inout [Int],_ startIn: Int,_ endIn: Int) -> TreeNode? {
        if  startIn > endIn {
            return nil
        }
        var root  = TreeNode(preOrder.removeFirst())
        for index in startIn...endIn {
            if inOrder[index] == root.val {
                root.left = recursive(&preOrder, &inOrder, startIn, index-1))
                root.right = recursive(&preOrder, &inOrder, index+1, endIn)
                 break
            }
        }
        return root
    }
}