April 18, 2024 4:45 AM (GMT+8)

先序序列第一个元素始终是 root ，中序序列的唯一作用只是划分先序序列。

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = inorder.size();
        for (int i = 0; i < n; i++) {
            map[inorder[i]] = i;
        }
        return build(preorder, 0, n - 1);
    }
private:
    unordered_map<int, int> map;
    int pos = 0;
    TreeNode* build(const vector<int>& preorder, int l, int r) {
        if (l > r) return nullptr;
        auto root = new TreeNode(preorder[pos++]);
        int pivot = map[preorder[pos]];
        root->left = build(preorder, l, pivot - 1);
        root->right = build(preorder, pivot + 1, r);
        return root;
    }
}

• old ver.

archive

以前的，用了哈希表简化搜索中序序列中根节点位置

首先从 preorder 第一个位置获得 root ，然后使用 root 划分中序序列，根据划分的长度递归向下确定 root （也就是上一个 root 的 root->left root->right）

class Solution {
private:
    unordered_map<int, int> pos;
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); i ++) {
            pos[inorder[i]] = i;
        }
        return build(preorder, 0, 0, inorder.size() - 1);
    }

    TreeNode* build(vector<int>& preorder, int root, int il, int ir) {
        if (il > ir) return nullptr;
        TreeNode* cur = new TreeNode(preorder[root]);
        int i = pos[preorder[root]];
        cur->left = build(preorder, root + 1, il, i - 1);
        cur->right = build(preorder, root + i - il + 1, i + 1,ir);
        return cur;
    }
};