Medium

题目描述

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

示例 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 <= inorder[i], postorder[i] <= 3000
  • inorder 和 postorder 都由不同的值组成
  • postorder 中每一个值都在 inorder 中
  • inorder 保证是树的中序遍历
  • postorder 保证是树的后序遍历

解题思路

这道题与从前序和中序遍历构造二叉树类似，核心思路是利用遍历序列的特点进行递归构造。

算法思路：

  1. 后序遍历特点：左子树 → 右子树 → 根节点，所以后序遍历的最后一个元素一定是根节点
  2. 中序遍历特点：左子树 → 根节点 → 右子树，根节点将中序遍历分为左右两部分
  3. 递归构造：
    • 从后序遍历末尾取根节点
    • 在中序遍历中找到根节点位置，确定左右子树的节点数量
    • 递归构造右子树（注意：由于后序遍历是左右根，我们先处理右子树）
    • 递归构造左子树

优化策略：

  • 使用哈希表存储中序遍历中每个值的索引，避免重复查找
  • 使用索引而不是创建新数组，减少空间开销

推荐解法：递归 + 哈希表优化，时间复杂度O(n)，空间复杂度O(n)

代码实现

class Solution {
private:
    unordered_map<int, int> inorderMap;
    int postIndex;
    
    TreeNode* buildTreeHelper(vector<int>& inorder, vector<int>& postorder, int inStart, int inEnd) {
        if (inStart > inEnd) return nullptr;
        
        int rootVal = postorder[postIndex--];
        TreeNode* root = new TreeNode(rootVal);
        
        int inIndex = inorderMap[rootVal];
        
        // 注意：后序遍历是左右根，所以先构造右子树
        root->right = buildTreeHelper(inorder, postorder, inIndex + 1, inEnd);
        root->left = buildTreeHelper(inorder, postorder, inStart, inIndex - 1);
        
        return root;
    }
    
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // 构建中序遍历的值到索引的映射
        for (int i = 0; i < inorder.size(); i++) {
            inorderMap[inorder[i]] = i;
        }
        
        postIndex = postorder.size() - 1;
        return buildTreeHelper(inorder, postorder, 0, inorder.size() - 1);
    }
};

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # 构建中序遍历的值到索引的映射
        inorder_map = {val: i for i, val in enumerate(inorder)}
        self.post_index = len(postorder) - 1
        
        def build_tree_helper(in_start, in_end):
            if in_start > in_end:
                return None
            
            root_val = postorder[self.post_index]
            self.post_index -= 1
            root = TreeNode(root_val)
            
            in_index = inorder_map[root_val]
            
            # 注意：后序遍历是左右根，所以先构造右子树
            root.right = build_tree_helper(in_index + 1, in_end)
            root.left = build_tree_helper(in_start, in_index - 1)
            
            return root
        
        return build_tree_helper(0, len(inorder) - 1)

public class Solution {
    private Dictionary<int, int> inorderMap;
    private int postIndex;
    
    public TreeNode BuildTree(int[] inorder, int[] postorder) {
        // 构建中序遍历的值到索引的映射
        inorderMap = new Dictionary<int, int>();
        for (int i = 0; i < inorder.Length; i++) {
            inorderMap[inorder[i]] = i;
        }
        
        postIndex = postorder.Length - 1;
        return BuildTreeHelper(inorder, postorder, 0, inorder.Length - 1);
    }
    
    private TreeNode BuildTreeHelper(int[] inorder, int[] postorder, int inStart, int inEnd) {
        if (inStart > inEnd) return null;
        
        int rootVal = postorder[postIndex--];
        TreeNode root = new TreeNode(rootVal);
        
        int inIndex = inorderMap[rootVal];
        
        // 注意：后序遍历是左右根，所以先构造右子树
        root.right = BuildTreeHelper(inorder, postorder, inIndex + 1, inEnd);
        root.left = BuildTreeHelper(inorder, postorder, inStart, inIndex - 1);
        
        return root;
    }
}

var buildTree = function(inorder, postorder) {
    // 构建中序遍历的值到索引的映射
    const inorderMap = new Map();
    for (let i = 0; i < inorder.length; i++) {
        inorderMap.set(inorder[i], i);
    }
    
    let postIndex = postorder.length - 1;
    
    function buildTreeHelper(inStart, inEnd) {
        if (inStart > inEnd) return null;
        
        const rootVal = postorder[postIndex--];
        const root = new TreeNode(rootVal);
        
        const inIndex = inorderMap.get(rootVal);
        
        // 注意：后序遍历是左右根，所以先构造右子树
        root.right = buildTreeHelper(inIndex + 1, inEnd);
        root.left = buildTreeHelper(inStart, inIndex - 1);
        
        return root;
    }
    
    return buildTreeHelper(0, inorder.length - 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历所有节点一次，哈希表查找为O(1)
空间复杂度O(n)哈希表存储空间O(n)，递归调用栈最坏情况O(n)

相关题目