力扣(LeetCode)106. 从中序与后序遍历序列构造二叉树(C++)

递归

如图，后序序列按照左右根遍历，所以根在最后。逆着后序遍历的顺序，按照根右左递归建树就可以复原这棵树。后序序列，可以确定根的位置 $postroot$ 和根结点的值。我们在中序序列找到根结点的值，就确定了根在中序序列的位置 $inroot$ 。那么，$inroot-1$ 往左就是左子树 , $inroot+1$ 往右就是右子树 ， 这是由于中序按照左根右顺序遍历。
我们按照根右左的顺序，递归建树即可。

• 细节补充

建立哈希表，预处理中序序列的结点值对应到下标。这样就可以 $O(1)$ 的从后序根结点值找到中序根结点下标了。
递归结束条件是建树的左右下标大小颠倒。

代码展示

class Solution {
private:
    unordered_map<int,int> mp;
    int postroot;
public:
    TreeNode* dfs(int inleft,int inright,vector<int> &inorder,vector<int> &postorder){
        if(inleft>inright) return NULL;
        // TreeNode *root = (TreeNode*)calloc(1,sizeof(TreeNode));
        // 力扣 delete 这棵树，对应 new , 不能calloc。
        int root_val = postorder[postroot--];
        TreeNode *root = new TreeNode(root_val);
        root->right = dfs(mp[root->val]+1,inright,inorder,postorder);
        root->left = dfs(inleft,mp[root->val]-1,inorder,postorder);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        postroot = (int)postorder.size()-1;
        int idx = 0;
        for(auto &x:inorder) mp[x] = idx++;
        return dfs(0,postroot,inorder,postorder);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC

复杂度分析

1. 时间复杂度: $O(n)$， $n$ 是 $inorder、postorder$ 的长度。递归建树的时间复杂度是 $O(n)$ 。
2. 空间复杂度: $O(n)$，递归的最坏深度是 $O(n)$ ，平均深度 $O(logn)$ 。