前序中序后序遍历恢复树

前序+中序恢复：

基于前序映射中序位置得到左右两侧长度，再反推前序left，right与中序left，right的位置。然后递归求root->left,right

class Solution {
public:
    TreeNode* build(vector<int>& preorder, vector<int>& inorder,int lp,int rp,int li,int ri){
        if(lp>rp||li>ri||lp>=preorder.size()||rp<0||li>=inorder.size()||ri<0){
            return nullptr;
        }
        
        TreeNode* root=new(TreeNode);
        root->val=preorder[lp];

        if(lp==rp){
            return root;
        }
        int i;
        for(i=li;i<=ri;i++){
            if(inorder[i]==preorder[lp]){
                break;
            }
        }
        int l=i-li;
        int r=ri-i;
        root->left=build(preorder,inorder,lp+1,lp+l,li,li+l-1);
        root->right=build(preorder,inorder,lp+l+1,rp,i+1,ri);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 中序 该点左右侧分开 前序 root
        return build(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
    }
};

或者使用map空间换时间

class Solution {
public:
    unordered_map<int,int>m;
    TreeNode* build(vector<int>& preorder, vector<int>& inorder,int lp,int rp,int li,int ri){
        if(lp>rp||li>ri||lp>=preorder.size()||rp<0||li>=inorder.size()||ri<0){
            return nullptr;
        }
        
        TreeNode* root=new(TreeNode);
        root->val=preorder[lp];

        if(lp==rp){
            return root;
        }
        int i=m[preorder[lp]];
        // for(i=li;i<=ri;i++){
        //     if(inorder[i]==preorder[lp]){
        //         break;
        //     }
        // }
        int l=i-li;
        int r=ri-i;
        root->left=build(preorder,inorder,lp+1,lp+l,li,li+l-1);
        root->right=build(preorder,inorder,lp+l+1,rp,i+1,ri);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 中序 该点左右侧分开 前序 root
        for(int i=0;i<inorder.size();i++){
            m[inorder[i]]=i;
        }
        return build(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
    }
};

中序后序

后序得到root节点，映射到中序位置，推算左右长度，

class Solution {
public:
    unordered_map<int,int>m;
    TreeNode* helper(vector<int>& inorder, vector<int>& postorder,int li,int ri,int lp,int rp){
        if(li>ri||lp>rp||li<0||ri>=inorder.size()||lp<0||rp>=postorder.size()){
            return nullptr;
        }
        TreeNode *root = new TreeNode();
        root->val=postorder[rp];

        int i=m[postorder[rp]];
        int l=i-li;
        int r=ri-i;
        root->left=helper(inorder,postorder,li,i-1,lp,lp+l-1);
        root->right=helper(inorder,postorder,i+1,ri,lp+l,rp-1);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        for(int i=0;i<inorder.size();i++){
            m[inorder[i]]=i;       
        }
        return helper(inorder,postorder,0,inorder.size()-1,0,postorder.size()-1);
    }
};

前序后序生成新合法序列

思路：preorder抛去第一位，postorder抛去最后一位，其他位的前N个元素如果乱序相等（abc==bca==acb），那么分别取lpre+1，lpre+1+i，lpost，lpost+i作为root->left的左递归，其他你懂的。

class Solution {
public:
    TreeNode* helper(vector<int>& pre, vector<int>& post,int lpre,int rpre,int lpost,int rpost){
        if(lpre>rpre||lpost>rpost||lpre<0||rpre>=pre.size()||lpost<0||rpost>=post.size()){
            return nullptr;
        }
        TreeNode* root=new(TreeNode);
        root->val=pre[lpre];
        if(lpre==rpre){
            return root;
        }
        int length=rpre-lpre-1;
        unordered_map<int,int>m1,m2;
        int presum=0;
        int postsum=0;
        int i;
        for(i=0;i<=length;i++){
            presum+=pre[lpre+1+i];
            m1[pre[lpre+1+i]]=1;
            postsum+=post[lpost+i];
            m2[post[lpost+i]]=1;
            if(postsum==presum){
                bool sign=true;
                for(auto k:m1){
                    if(m2.count(k.first)==0){
                        sign=false;
                        break;
                    }
                }
                if(sign==true){
                    break;
                }
            }
        }
        root->left=helper(pre,post,lpre+1,lpre+i+1,lpost,lpost+i);
        root->right=helper(pre,post,lpre+i+2,rpre,lpost+i+1,rpost-1);
        return root;
    }
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        return helper(pre,post,0,pre.size()-1,0,post.size()-1);
    }
};

用map可以优化，取preorder [1:N] 第一个元素对应在postorder [0:N-1]上的位置作为对应点，从而快速获得解。

class Solution {
public:
    unordered_map<int,int>m;
    TreeNode* helper(vector<int>& pre, vector<int>& post,int lpre,int rpre,int lpost,int rpost){
        if(lpre>rpre||lpost>rpost||lpre<0||rpre>=pre.size()||lpost<0||rpost>=post.size()){
            return nullptr;
        }
        TreeNode* root=new(TreeNode);
        root->val=pre[lpre];
        if(lpre==rpre){
            return root;
        }
        int i=m[pre[lpre+1]];
        int l=i-lpost;
        root->left=helper(pre,post,lpre+1,lpre+1+l,lpost,i);
        root->right=helper(pre,post,lpre+l+2,rpre,i+1,rpost-1);
        return root;
    }
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        for(int i=0;i<post.size();i++){
            m[post[i]]=i;
        }
        return helper(pre,post,0,pre.size()-1,0,post.size()-1);
    }
};