8-liner recursion, no stack (with comments)


  • 0

    The key is to location the substring from s to represent left subtree, then the substring before and after left subtree will represent root and right subtree, respectively.

        TreeNode* str2tree(string s) {
          auto b = s.begin(), e = s.end(), i = find(b,e,'('), j = i; // i: first '('
          auto r = s.empty()? NULL : new TreeNode(stoi(string(b,i))); // build root     
          if (i < e) { // s contains brackets
            int d = 0; // count difference of '(' and ')' in left subtree
            while (*j == '('? ++d : *j == ')'? --d : d) ++j; // find end ')' of left subtree
        
            r->left  = str2tree(string(++i, j)); 
            r->right = j+2<e? str2tree(string(j+2, e-1)) : NULL;
          }
          return r;
        }
    

Log in to reply
 

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