Medium

题目描述

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

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder 和 inorder 均无重复元素
  • inorder 均出现在 preorder 中
  • preorder 保证为二叉树的前序遍历序列
  • inorder 保证为二叉树的中序遍历序列

解题思路

这是一道经典的树构造问题，关键在于理解前序遍历和中序遍历的特点：

核心思路：

  • 前序遍历的第一个元素总是根节点
  • 在中序遍历中找到根节点的位置，左边是左子树，右边是右子树
  • 递归构造左右子树

算法步骤：

  1. 如果数组为空，返回 null
  2. 前序遍历的第一个元素作为根节点
  3. 在中序遍历中找到根节点的位置（可用哈希表优化）
  4. 根据根节点在中序遍历中的位置，确定左右子树的节点数量
  5. 递归构造左子树和右子树

优化技巧： 使用哈希表存储中序遍历中每个值的索引，将查找时间从 O(n) 优化到 O(1)。这是推荐的解法，时间复杂度为 O(n)，空间复杂度为 O(n)。

另一种解法是直接在数组中查找，但时间复杂度会退化到 O(n²)。

代码实现

class Solution {
private:
    unordered_map<int, int> inorderMap;
    int preorderIndex = 0;
    
    TreeNode* build(vector<int>& preorder, int left, int right) {
        if (left > right) return nullptr;
        
        int rootVal = preorder[preorderIndex++];
        TreeNode* root = new TreeNode(rootVal);
        
        int inorderIndex = inorderMap[rootVal];
        
        root->left = build(preorder, left, inorderIndex - 1);
        root->right = build(preorder, inorderIndex + 1, right);
        
        return root;
    }
    
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); i++) {
            inorderMap[inorder[i]] = i;
        }
        return build(preorder, 0, inorder.size() - 1);
    }
};

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        inorder_map = {val: i for i, val in enumerate(inorder)}
        self.preorder_idx = 0
        
        def build(left, right):
            if left > right:
                return None
            
            root_val = preorder[self.preorder_idx]
            self.preorder_idx += 1
            root = TreeNode(root_val)
            
            inorder_idx = inorder_map[root_val]
            
            root.left = build(left, inorder_idx - 1)
            root.right = build(inorder_idx + 1, right)
            
            return root
        
        return build(0, len(inorder) - 1)

public class Solution {
    private Dictionary<int, int> inorderMap;
    private int preorderIndex = 0;
    
    public TreeNode BuildTree(int[] preorder, int[] inorder) {
        inorderMap = new Dictionary<int, int>();
        for (int i = 0; i < inorder.Length; i++) {
            inorderMap[inorder[i]] = i;
        }
        return Build(preorder, 0, inorder.Length - 1);
    }
    
    private TreeNode Build(int[] preorder, int left, int right) {
        if (left > right) return null;
        
        int rootVal = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootVal);
        
        int inorderIndex = inorderMap[rootVal];
        
        root.left = Build(preorder, left, inorderIndex - 1);
        root.right = Build(preorder, inorderIndex + 1, right);
        
        return root;
    }
}

var buildTree = function(preorder, inorder) {
    const inorderMap = new Map();
    for (let i = 0; i < inorder.length; i++) {
        inorderMap.set(inorder[i], i);
    }
    
    let preorderIndex = 0;
    
    function build(left, right) {
        if (left > right) return null;
        
        const rootVal = preorder[preorderIndex++];
        const root = new TreeNode(rootVal);
        
        const inorderIndex = inorderMap.get(rootVal);
        
        root.left = build(left, inorderIndex - 1);
        root.right = build(inorderIndex + 1, right);
        
        return root;
    }
    
    return build(0, inorder.length - 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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

相关题目