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

淩亂°似流年 2022-10-13 02:50 16阅读 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 *helper(vector<int>& pre, vector<int>& in) {
            if(pre.size()==0 && in.size()==0) return nullptr;
            TreeNode *root=new TreeNode(pre[0]);
            if(pre.size()==1 && in.size()==1) {
                root->left=nullptr;
                root->right=nullptr;
                return root;
            }
    
            auto it=find(in.begin(),in.end(),pre[0]);
            int index=it-in.begin();
            
            vector<int> l_pre,l_in,r_pre,r_in;
            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=1;i<pre.size();i++) {
                if(i<=index) l_pre.push_back(pre[i]);
                else r_pre.push_back(pre[i]);
            }
            
            root->left=helper(l_pre,l_in);
            root->right=helper(r_pre,r_in);
            
            return root;
        }
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            return helper(preorder,inorder);
        }
    };