题解 | 重建二叉树

1、解题思路

1. 前序遍历：根节点 -> 左子树 -> 右子树。
2. 中序遍历：左子树 -> 根节点 -> 右子树。
3. 重建步骤：前序遍历的第一个元素是根节点。在中序遍历中找到根节点的位置，左侧是左子树，右侧是右子树。递归构建左子树和右子树。

2、代码实现

C++

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <unordered_map>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param preOrder int整型vector
     * @param vinOrder int整型vector
     * @return TreeNode类
     */
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        // write code here
        unordered_map<int, int> vinMap;
        // 存储中序遍历和值索引, 方便快速查找根节点位置
        for (int i = 0; i < vinOrder.size(); ++i) {
            vinMap[vinOrder[i]] = i;
        }
        return buildTree(preOrder, 0, preOrder.size() - 1, vinOrder, 0,
                         vinOrder.size() - 1, vinMap);
    }

    TreeNode* buildTree(vector<int>& preOrder, int preStart, int preEnd,
                        vector<int>& vinOrder, int vinStart, int vinEnd,
                        unordered_map<int, int>& vinMap) {
        if (preStart > preEnd || vinStart > vinEnd) {
            return nullptr;
        }

        // 前序遍历的第一个节点是根节点
        int rootVal = preOrder[preStart];
        TreeNode* root = new TreeNode(rootVal);

        // 在中序遍历中找到根节点的位置
        int rootIndex = vinMap[rootVal];
        int leftSubtreeSize = rootIndex - vinStart;

        // 递归构建左子树
        root->left = buildTree(preOrder, preStart + 1, preStart + leftSubtreeSize,
                               vinOrder, vinStart, rootIndex - 1, vinMap);

        // 递归构建右子树
        root->right = buildTree(preOrder, preStart + leftSubtreeSize + 1, preEnd,
                                vinOrder, rootIndex + 1, vinEnd, vinMap);

        return root;
    }
};

Java

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    private HashMap<Integer, Integer> vinMap = new HashMap<>();

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param preOrder int整型一维数组
     * @param vinOrder int整型一维数组
     * @return TreeNode类
     */
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        // write code here
        // 存储中序遍历的值和索引
        for (int i = 0; i < vinOrder.length; i++) {
            vinMap.put(vinOrder[i], i);
        }
        return buildTree(preOrder, 0, preOrder.length - 1, vinOrder, 0,
                         vinOrder.length - 1);
    }

    private TreeNode buildTree(int[] preOrder, int preStart, int preEnd,
                               int[] vinOrder, int vinStart, int vinEnd) {
        if (preStart > preEnd || vinStart > vinEnd) {
            return null;
        }

        // 前序遍历的第一个节点是根节点
        int rootVal = preOrder[preStart];
        TreeNode root = new TreeNode(rootVal);

        // 在中序遍历中找到根节点的位置
        int rootIndex = vinMap.get(rootVal);
        int leftSubtreeSize = rootIndex - vinStart;

        // 递归构建左子树
        root.left = buildTree(preOrder, preStart + 1, preStart + leftSubtreeSize,
                              vinOrder, vinStart, rootIndex - 1);

        // 递归构建右子树
        root.right = buildTree(preOrder, preStart + leftSubtreeSize + 1, preEnd,
                               vinOrder, rootIndex + 1, vinEnd);

        return root;
    }


}

Python

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param preOrder int整型一维数组 
# @param vinOrder int整型一维数组 
# @return TreeNode类
#
class Solution:
    def reConstructBinaryTree(self , preOrder: List[int], vinOrder: List[int]) -> TreeNode:
        # write code here
        # 存储中序遍历的值和索引
        vin_map = {val: idx for idx, val in enumerate(vinOrder)}
        return self.buildTree(preOrder, 0, len(preOrder) - 1, vinOrder, 0, len(vinOrder) - 1, vin_map)
    
    def buildTree(self, preOrder, preStart, preEnd, vinOrder, vinStart, vinEnd, vin_map):
        if preStart > preEnd or vinStart > vinEnd:
            return None
        
        # 前序遍历的第一个节点是根节点
        root_val = preOrder[preStart]
        root = TreeNode(root_val)
        
        # 在中序遍历中找到根节点的位置
        root_index = vin_map[root_val]
        left_subtree_size = root_index - vinStart
        
        # 递归构建左子树
        root.left = self.buildTree(preOrder, preStart + 1, preStart + left_subtree_size, 
                                 vinOrder, vinStart, root_index - 1, vin_map)
        
        # 递归构建右子树
        root.right = self.buildTree(preOrder, preStart + left_subtree_size + 1, preEnd, 
                                  vinOrder, root_index + 1, vinEnd, vin_map)
        
        return root

3、复杂度分析

1. 时间复杂度：O(n)，每个节点访问一次。
2. 空间复杂度：O(n)，存储中序遍历的哈希表。