继续创作，加快成长！这是我参与「日新方案 6 月更文挑战」的第22天，点击检查活动概况

前语

咱们社区连续会将顾毅（Netflix 增加黑客，《iOS 面试之道》作者，ACE 职业健身教练。）的 Swift 算法题题解收拾为文字版以方便咱们学习与阅读。

LeetCode 算法到现在咱们现已更新到 105 期，咱们会保持更新时刻和进展（周一、周三、周五早上 9:00 发布），每期的内容不多，咱们希望咱们可以在上班路上阅读，长久堆集会有很大提升。

不积跬步，无以致千里；不积小流，无以成江海，Swift社区 伴你前行。如果咱们有建议和意见欢迎在文末留言，咱们会极力满足咱们的需求。

难度水平：中等

1. 描述

给定两个整数数组 inorder 和 postorder ，其间 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

2. 示例

示例 1

LeetCode - #106 从中序与后序遍历序列构造二叉树

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2

输入：inorder = [-1], postorder = [-1]
输出：[-1]

约束条件：

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorder 和 postorder 都由 不同 的值组成
  • postorder 中每一个值都在 inorder 中
  • inorder 确保是树的中序遍历
  • postorder 确保是树的后序遍历

3. 答案

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class ConstructBinaryTreeInorderPostorder {
    func buildTree(inorder: [Int], _ postorder: [Int]) -> TreeNode? {
        guard inorder.count > 0 && postorder.count > 0 && inorder.count == postorder.count else {
            return nil
        }
        return _buildHelper(inorder, 0, inorder.count - 1, postorder, 0, postorder.count - 1)
    }
    private func _buildHelper(inorder: [Int], _ inStart: Int, _ inEnd: Int, _ postorder: [Int], _ postStart: Int, _ postEnd: Int) -> TreeNode? {
        guard inStart <= inEnd && postStart <= postEnd else {
            return nil
        }
        let root = TreeNode(postorder[postEnd])
        var mid = 0
        for i in inStart...inEnd where inorder[i] == root.val {
            mid = i
            break
        }
        root.left = _buildHelper(inorder, inStart, mid - 1, postorder, postStart, mid - 1 - inStart + postStart)
        root.right = _buildHelper(inorder, mid + 1, inEnd, postorder, mid - inStart + postStart, postEnd - 1)
        return root
    }
}
  • 主要思维：总是使用 postorder 中的最终一个元素作为根，然后找到这个元素以便取得左子树和右子树。
  • 时刻复杂度： O(nlogn)
  • 空间复杂度： O(1)

该算法题解的仓库：LeetCode-Swift

点击前往 LeetCode 练习

关于咱们

咱们是由 Swift 爱好者一起维护，咱们会分享以 Swift 实战、SwiftUI、Swift 基础为中心的技术内容，也收拾搜集优异的学习资料。

后续还会翻译大量资料到咱们公众号，有感爱好的朋友，可以参加咱们。