LeetCode习题：根据前序和后序遍历构造二叉树

题目描述：返回与给定的前序和后序遍历匹配的任何二叉树。pre 和 post 遍历中的值是不同的正整数

示例：

输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

提示：

• 1 <= pre.length == post.length <= 30
• pre[] 和 post[] 都是 1, 2, …, pre.length 的排列
• 每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。

题解：递归(以下解题思路来自LeetCode官方题解)

解题思路：前序遍历为：

• (根结点) (前序遍历左分支) (前序遍历右分支)

而后序遍历为：

• (后序遍历左分支) (后序遍历右分支) (根结点)

例如，如果最终的二叉树可以被序列化的表述为 [1, 2, 3, 4, 5, 6, 7]，那么其前序遍历为 [1] + [2, 4, 5] + [3, 6, 7]，而后序遍历为 [4, 5, 2] + [6, 7, 3] + [1].如果我们知道左分支有多少个结点，我们就可以对这些数组进行分组，并用递归生成树的每个分支。

算法：

我们令左分支有 L 个节点。我们知道左分支的头节点为 pre[1]，但它也出现在左分支的后序表示的最后。所以 pre[1] = post[L-1]（因为结点的值具有唯一性），因此 L = post.indexOf(pre[1]) + 1。现在在我们的递归步骤中，左分支由 pre[1 : L+1] 和 post[0 : L] 重新分支，而右分支将由 pre[L+1 : N] 和 post[L : N-1] 重新分支。

解题语言： Swift

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val4
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func constructFromPrePost(_ pre: [Int], _ post: [Int]) -> TreeNode? {
        let pLength = pre.count
        if (pLength == 0) {
            return nil
        }
        var root = TreeNode(pre[0])
        if (pLength == 1) {
            return root
        }

        var L = 0
        for (i, item) in pre.enumerated() {
            if (post[i] == pre[1]) {
                L = i + 1
            }
        }
        root.left = constructFromPrePost(Array(pre[1..<L+1]), Array(post[0..<L]))
        root.right = constructFromPrePost(Array(pre[L+1..<pLength]), Array(post[L..<pLength-1]))
        return root
    }
}

复杂度分析：

时间复杂度：O(N^2)，其中 N 是结点的数量。

空间复杂度：O(N^2)。

题目来源：LeetCode