剑指offer—面试题7：重建该二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，
给出前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

给出的数结点结构如下：

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

根据树的遍历特性，前序遍历每次都会访问根节点然后访问左子树的结点、右子树几点。中序遍历则会先遍历左子树节点、根节点、右子树节点。所以前序遍历的结果的第一个数字就是数的根节点。在中序遍历结果中根节点的左侧数据属于左子树、右侧数据属于右子树。

image.png

通过以上三步，可确定三个结点，第一步确定树的根节点，第二步划分左右子树的节点个数。第三步确定左右子树的根节点（如果左子树节点个数大于0，则前序遍历中左子树的根节点紧跟树的根节点。右子树的根节点在前序遍历结果中右子树的根节点位域左子树个数+1）。接下来我们就可以用递归的方式完成重建。

暴力算法

 func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
        if preorder.count == 0 {
            return nil
        }
        let headValue = preorder.first!
        let headNode: TreeNode? = TreeNode(headValue)
        
        for (index,value) in inorder.enumerated() {
            if value == headValue  {
                headNode?.left = buildTree(Array(preorder[1..<index+1]),Array(inorder[0..<index]))
                headNode?.right = buildTree(Array(preorder[index+1..<preorder.endIndex]),Array(inorder[index+1..<inorder.endIndex]))
            }
        }
        return headNode
    }

递归的另一种解法

   var inIndex = 0
    var preIndex = 0
    
    func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
        if preorder.count == 0 || inorder.count == 0 {
            return nil
        }
        return build(preorder, inorder,Int.max)
    }
        
    func build(_ preorder: [Int], _ inorder: [Int],_ stop: Int) -> TreeNode? {
        if preIndex >= preorder.count {
            return nil
        }
        if inorder[inIndex] == stop {
            inIndex += 1
            return nil
        }
        
        let node = TreeNode(preorder[preIndex])
        preIndex += 1
        node.left = build(preorder, inorder, node.val)
        node.right = build(preorder, inorder, stop)
        return node
    }