My C++ recursion method easily understand


  • 0
    D
    class Solution {
    public:
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            TreeNode* root_tmp=new TreeNode(0);
            recursion_buildTree(preorder,inorder,root_tmp,0,preorder.size()-1,0,inorder.size()-1,1);
            return root_tmp->left;
        }
        void recursion_buildTree(vector<int>& preorder,vector<int>& inorder, TreeNode* cur, int prebegin,int preend, int inbegin,int inend,int flag){
            if(preend<prebegin) return;
            if(flag) {cur->left=new TreeNode(preorder[prebegin]);cur=cur->left;}
            else {cur->right=new TreeNode(preorder[prebegin]);cur=cur->right;}
            if(preend==prebegin) return;
            int cur_val=preorder[prebegin],pos;
            for(int i=inbegin;i<=inend;i++) {if(inorder[i]==cur_val) {pos=i;break;}}
            recursion_buildTree(preorder,inorder,cur,prebegin+1,pos-inbegin+prebegin,inbegin,pos-1,1);
            recursion_buildTree(preorder,inorder,cur,pos-inbegin+prebegin+1,preend,pos+1,inend,0);
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.