(模板必背)根据二叉树的前序(后序)和中序遍历建立二叉树

向右看齐 2022-11-19 07:51 64阅读 0赞

根据前序和中序建树

class Solution {
    public:
        unordered_map<int,int> pos;
        TreeNode* build(vector<int>& preorder, vector<int>& inorder,int il,int ir,int pl,int pr){
            if(il > ir) return nullptr;
            TreeNode* root = new TreeNode(preorder[pl]);
            int k = pos[root->val];
            root->left = build(preorder,inorder,il,k-1,pl+1,pl+k-il);
            root->right = build(preorder,inorder,k+1,ir,pl+k-il+1,pr);
            return root;
        }
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            int n = inorder.size();
            for(int i = 0; i < inorder.size();++i){
                pos[inorder[i]] = i;
            }
            return build(preorder,inorder,0,n-1,0,n-1);
        }
    };

根据中序和后序建树

class Solution {
    public:
        vector<int> sinorder,spostorder;
        unordered_map<int,int> pos;
        TreeNode* build(int il,int ir,int pl,int pr){
            if(il > ir) return nullptr;
            TreeNode* root = new TreeNode(spostorder[pr]);
            int k = pos[root->val];
            root->left = build(il,k-1,pl,pl+(k-1-il));
            root->right = build(k+1,ir,pl+(k-1-il)+1,pr-1); 
            return root;
        }
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            int n = inorder.size();
            sinorder = inorder;
            spostorder = postorder; //赋值
            for(int i = 0; i < inorder.size(); ++i){
                pos[inorder[i]] = i;   //中序数组定位
            }
            return build(0,n-1,0,n-1);
        }
    };