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

前言

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

LeetCode 算法到目前我们已经更新到 105 期，我们会保持更新时间和进度（周一、周三、周五早上 9:00 发布），每期的内容不多，我们希望大家可以在上班路上阅读，长久积累会有很大提升。

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

难度水平：中等

1. 描述

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

2. 示例

示例 1

输入：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 基础为核心的技术内容，也整理收集优秀的学习资料。

后续还会翻译大量资料到我们公众号，有感兴趣的朋友，可以加入我们。