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

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

递归解法

• 时间复杂度
  O(n) n 是节点的个数，每个节点都访问一次
• 空间复杂度
  O(n) 除去返回的答案需要的 O(n) 空间之外，我们还需要使用 O(n) 的空间存储哈希映射，以及 O(h)（其中 h 是树的高度）的空间表示递归时栈空间。这里 h < n，所以总空间复杂度为 O(n)。

var inorderMap: [Int: Int] = [:]

    func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
        let count = preorder.count
        // 这一步是为了节省时间 但是增加了空间占用
        for (index, val) in inorder.enumerated() {
            inorderMap[val] = index
        }
        return myBuildTree(preorder, inorder, 0, count - 1, 0, count - 1)
    }

    func myBuildTree(_ preorder: [Int], _ inorder: [Int], _ preorderLeft: Int, _ preorderRight: Int, _ inorderLeft: Int, _ inorderRight: Int) -> TreeNode? {
        if preorderLeft > preorderRight {
            return nil
        }
        // 前序遍历的第一个节点就是根节点
        let preorderRoot = preorderLeft
        // 找出中序遍历的根节点位置
        let inorderRoot = inorderMap[preorder[preorderRoot]]!
        // 先把根节点建立出来
        let root = TreeNode(preorder[preorderRoot])
        // 左子树的节点数目
        let leftTreeCount = inorderRoot - inorderLeft

        // 递归地构造左子树，并连接到根节点
        // 前序遍历中从 [preorderLeft + 1 开始的 leftTreeCount 个元素就是 当前 root 左子树的所有节点
        // 中序遍历中从 [inorderLeft 开始到 inorderRoot - 1]  就是当前 root 左子树的 所有节点

        root.left = myBuildTree(preorder, inorder, preorderLeft + 1, preorderLeft + leftTreeCount, inorderLeft, inorderRoot - 1)

        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        // 前序遍历中从 [preorderRoot + 1(这个1是根节点的长度) + leftTreeCount 到 preorderRight] 是当前 root 右子树的所有节点
        // 中序遍历中从 [inorderRoot + 1 到 inorderRight] 是当前 root 右子树的所有节点
        root.right = myBuildTree(preorder, inorder, preorderRoot + 1 + leftTreeCount, preorderRight, inorderRoot + 1, inorderRight)

        return root
    }