https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

根据一棵树的中序遍历与后序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。
示例

First Solution:
初解，盯着示例1想出来的构造，我也不知道为啥想到用指针(于是后面优化成了下标)

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
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0) return nullptr;
        auto p_in = inorder.begin(), p_post = postorder.begin();
        TreeNode *tmp_left;
        if (*p_in == *p_post) {
            tmp_left = new TreeNode;
            tmp_left->val = *p_in;
            p_in++;
            p_post++;
        }
        else tmp_left = nullptr;
        while(p_post != postorder.end()) {
            auto tmp_p_post = p_post, tmp_p_in = p_in;
            while(*p_post != *p_in) {
                p_post++;
                tmp_p_in++;
            }
            TreeNode *tmp_mid = new TreeNode;
            tmp_mid->val = *p_in;
            tmp_mid->left = tmp_left;
            p_in++;
            tmp_p_in++;
            vector<int> new_inorder = {p_in, tmp_p_in}, new_postorder = {tmp_p_post, p_post};
            tmp_mid->right = buildTree(new_inorder, new_postorder);
            tmp_left = tmp_mid;
            p_post++;
            p_in = tmp_p_in;
        }
        return tmp_left;
    }
};

Second Solution:
看到题解使用哈希表优化查找过程，于是我也照着改了一版

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
class Solution {
private:
    unordered_map<int,int> idx_map;
    vector<int> inorder, postorder;
    TreeNode* helper(int in_beg, int post_beg, int length) {
        if (length == 0) return nullptr;
        int p_in = in_beg, p_post = post_beg;
        TreeNode *tmp_left;
        if (inorder[p_in] == postorder[p_post]) {
            tmp_left = new TreeNode;
            tmp_left->val = inorder[p_in];
            p_in++;
            p_post++;
        }
        else tmp_left = nullptr;
        while(p_post != post_beg + length) {
            p_post = idx_map[inorder[p_in]];
            TreeNode *tmp_mid = new TreeNode;
            tmp_mid->val = inorder[p_in];
            tmp_mid->left = tmp_left;
            tmp_mid->right = helper(p_in + 1, p_in + post_beg - in_beg, p_post - p_in + in_beg - post_beg);
            tmp_left = tmp_mid;
            p_post++;
            p_in = p_post + in_beg - post_beg;
        }
        return tmp_left;
    }
public:
    TreeNode* buildTree(vector<int>& _inorder, vector<int>& _postorder) {
        inorder = _inorder;
        postorder = _postorder;
        int length = postorder.size();
        for(int i = 0; i < length; i++) idx_map[postorder[i]] = i;
        return helper(0, 0, length);
    }
};

可见下标维护十分混乱，改出这坨来真是累死了

Final Solution:
正确的递归做法还应该是从后序遍历的末尾不断获得根节点来截中序遍历为左右子树的序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
private:
    unordered_map<int,int> idx_map;
    vector<int> inorder, postorder;
    int post_idx;
    TreeNode* helper(int in_beg, int in_end) {
        if (in_beg > in_end) return nullptr;
        int root_val = postorder[post_idx--];
        int index = idx_map[root_val];
        TreeNode *root = new TreeNode(root_val);
        root->right = helper(index + 1, in_end);
        root->left = helper(in_beg, index - 1);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& _inorder, vector<int>& _postorder) {
        inorder = _inorder;
        postorder = _postorder;
        int length = postorder.size();
        post_idx = length - 1;
        for(int i = 0; i < length; i++) idx_map[inorder[i]] = i;
        return helper(0, length - 1);
    }
};