面试题07. 重建二叉树

https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/

var inDic = Dictionary<Int, Int>()
var preNodes = [Int]()

func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
    if preorder.count <= 0 || inorder.count <= 0 {return nil}
    for (idx, value) in inorder.enumerated() {
        inDic.updateValue(idx, forKey: value)
    }
    preNodes = preorder
    return reBuildTree(0, 0, inorder.count - 1)
}
//前序遍历根节点idx，中序遍历子树左右边界
func reBuildTree(_ preRootIdx: Int, _ left: Int, _ right: Int) -> TreeNode? {
    if left > right {return nil}
    let preRoot = preNodes[preRootIdx]//前序遍历中的当前根节点值
    let root = TreeNode(preRoot)//创建根节点
    let inRootIdx = inDic[preRoot]!//根节点在中序遍历的下标
    
    root.left = reBuildTree(preRootIdx + 1, left, inRootIdx - 1)
    // 前序遍历右子树的根节点idx =   左子节点的数量   + 前序根节点idx + 1
    root.right = reBuildTree(inRootIdx - left + preRootIdx + 1, inRootIdx + 1, right)
    return root
}