Medium

题目描述

给定两个整数数组，preorder 和 postorder，其中 preorder 是一个具有不同值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，请重新构造并返回这个二叉树。

如果存在多个答案，您可以返回其中的任何一个。

示例 1：

输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

示例 2：

输入：preorder = [1], postorder = [1]
输出：[1]

提示：

  • 1 <= preorder.length <= 30
  • 1 <= preorder[i] <= preorder.length
  • preorder 的所有值都是唯一的
  • postorder.length == preorder.length
  • 1 <= postorder[i] <= postorder.length
  • postorder 的所有值都是唯一的
  • 保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历

解题思路

这道题的关键在于理解前序遍历和后序遍历的特点：

  • 前序遍历：根 -> 左子树 -> 右子树
  • 后序遍历：左子树 -> 右子树 -> 根

核心思路：

  1. 确定根节点：前序遍历的第一个元素和后序遍历的最后一个元素都是根节点

  2. 划分左右子树：如果左子树非空，前序遍历中根节点后的第一个元素就是左子树的根。在后序遍历中找到这个左子树根的位置，就能确定左子树的大小

  3. 递归构造：根据左子树的大小，可以将前序和后序数组分割成对应的左子树和右子树部分，然后递归构造

实现细节：

  • 使用哈希表优化在后序数组中查找元素位置的过程
  • 当只有一个节点时直接返回
  • 当左子树为空时，整个子树就是右子树

这种方法的时间复杂度为O(n)，空间复杂度为O(n)，是最优解。

代码实现

class Solution {
public:
    unordered_map<int, int> postMap;
    
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        for (int i = 0; i < postorder.size(); i++) {
            postMap[postorder[i]] = i;
        }
        return build(preorder, 0, preorder.size() - 1, postorder, 0, postorder.size() - 1);
    }
    
    TreeNode* build(vector<int>& preorder, int preStart, int preEnd, 
                   vector<int>& postorder, int postStart, int postEnd) {
        if (preStart > preEnd) return nullptr;
        
        TreeNode* root = new TreeNode(preorder[preStart]);
        
        if (preStart == preEnd) return root;
        
        int leftRootVal = preorder[preStart + 1];
        int leftRootPostIdx = postMap[leftRootVal];
        int leftSize = leftRootPostIdx - postStart + 1;
        
        root->left = build(preorder, preStart + 1, preStart + leftSize,
                          postorder, postStart, leftRootPostIdx);
        root->right = build(preorder, preStart + leftSize + 1, preEnd,
                           postorder, leftRootPostIdx + 1, postEnd - 1);
        
        return root;
    }
};

class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        self.post_map = {val: idx for idx, val in enumerate(postorder)}
        
        def build(pre_start, pre_end, post_start, post_end):
            if pre_start > pre_end:
                return None
            
            root = TreeNode(preorder[pre_start])
            
            if pre_start == pre_end:
                return root
            
            left_root_val = preorder[pre_start + 1]
            left_root_post_idx = self.post_map[left_root_val]
            left_size = left_root_post_idx - post_start + 1
            
            root.left = build(pre_start + 1, pre_start + left_size,
                             post_start, left_root_post_idx)
            root.right = build(pre_start + left_size + 1, pre_end,
                              left_root_post_idx + 1, post_end - 1)
            
            return root
        
        return build(0, len(preorder) - 1, 0, len(postorder) - 1)

public class Solution {
    private Dictionary<int, int> postMap;
    
    public TreeNode ConstructFromPrePost(int[] preorder, int[] postorder) {
        postMap = new Dictionary<int, int>();
        for (int i = 0; i < postorder.Length; i++) {
            postMap[postorder[i]] = i;
        }
        
        return Build(preorder, 0, preorder.Length - 1, postorder, 0, postorder.Length - 1);
    }
    
    private TreeNode Build(int[] preorder, int preStart, int preEnd,
                          int[] postorder, int postStart, int postEnd) {
        if (preStart > preEnd) return null;
        
        TreeNode root = new TreeNode(preorder[preStart]);
        
        if (preStart == preEnd) return root;
        
        int leftRootVal = preorder[preStart + 1];
        int leftRootPostIdx = postMap[leftRootVal];
        int leftSize = leftRootPostIdx - postStart + 1;
        
        root.left = Build(preorder, preStart + 1, preStart + leftSize,
                         postorder, postStart, leftRootPostIdx);
        root.right = Build(preorder, preStart + leftSize + 1, preEnd,
                          postorder, leftRootPostIdx + 1, postEnd - 1);
        
        return root;
    }
}

var constructFromPrePost = function(preorder, postorder) {
    if (preorder.length === 0) return null;
    
    const root = new TreeNode(preorder[0]);
    if (preorder.length === 1) return root;
    
    const leftRootVal = preorder[1];
    const leftRootIdxInPost = postorder.indexOf(leftRootVal);
    const leftSize = leftRootIdxInPost + 1;
    
    root.left = constructFromPrePost(
        preorder.slice(1, 1 + leftSize),
        postorder.slice(0, leftSize)
    );
    root.right = constructFromPrePost(
        preorder.slice(1 + leftSize),
        postorder.slice(leftSize, -1)
    );
    
    return root;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个节点访问一次，哈希表查找为O(1)
空间复杂度O(n)哈希表存储n个元素，递归栈深度最坏为O(n)