Construct Binary Tree from Inorder and Postorder Traversal（C++从中序与后序遍历序列构造二叉树）

我就是我 2022-10-13 02:58 21阅读 0赞

（1）递归+二叉树

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        TreeNode* buildTree(vector<int>& in, vector<int>& post) {
            if(in.size()==0 && post.size()==0) return nullptr;
            TreeNode *root=new TreeNode(post[post.size()-1]);
            if(in.size()==1 && post.size()==1) {
                root->left=nullptr;
                root->right=nullptr;
                return root;
            }
        
            auto it=find(in.begin(),in.end(),post[post.size()-1]);
            int index=it-in.begin();
            
            vector<int> l_in,l_post,r_in,r_post;
            for(int i=0;i<in.size();i++) {
                if(i<index) l_in.push_back(in[i]);
                else if(i>index) r_in.push_back(in[i]);
            }
            
            for(int i=0;i<post.size()-1;i++) {
                if(i<index) l_post.push_back(post[i]);
                else r_post.push_back(post[i]);
            }
            
            root->left=buildTree(l_in,l_post);
            root->right=buildTree(r_in,r_post);
            
            return root;
        }
    };