18. 重建二叉树 - AcWing题库

输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。

注意:

二叉树中每个节点的值都互不相同；
输入的前序遍历和中序遍历一定合法；

数据范围
树中节点数量范围[0,100]。

样例

1
2
3
4
5
6
7
8
9
10
11
给定：
前序遍历是：[3, 9, 20, 15, 7]
中序遍历是：[9, 3, 15, 20, 7]

返回：[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示：
    3
   / \
  9  20
    /  \
   15   7

算法思路

image-20230404193839718

image-20230404204620577

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    
    unordered_map<int,int> pos;
    
    TreeNode * build(vector<int>& preorder, vector<int>& inorder, int a, int b, int x, int y){
        // 如果区间为空（若 a == b ，比如 9 == 9，此时依旧要创建 根为9 的节点）
        if(a > b) return NULL;
        
        // 先构建根节点
        TreeNode * root = new TreeNode(preorder[a]);
        // 找到中序遍历中根节点的位置
        int k = pos[root -> val];
        // 递归创建左子树和右子树
        root -> left = build(preorder, inorder, a + 1, k - x + a, x, k - 1);
        root -> right = build(preorder, inorder, b - y + k + 1, b, k + 1, y);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int len = inorder.size();
        // 提前记录中序遍历每个元素的位置
        for(int i = 0; i < len; i++) pos[inorder[i]] = i;
        
        return build(preorder, inorder, 0, len - 1, 0, len - 1);
    }
};

时间复杂度：O(n)