AC cpp recursive and iterative solution


  • 0
    M
    TreeNode* str2treeHelper(string s, int& idx, int n) {
      int start = idx;
      int cnt = 0;
      int neg = 1;
      if (s[idx] == '-') {
    	idx++;
    	start++;
    	neg = -1;
      }
      while (idx < n && isdigit(s[idx])) {
    	idx++;
      }
      if (idx == start) {
    	return nullptr;
      }
      string val = s.substr(start, idx - start);
      TreeNode* root = new TreeNode(stoi(val) * neg);
      while (idx < n) {
    	if (s[idx] == '(') {
    	  cnt++;
    	  idx++;
    	  if (cnt == 1) {
    		root->left = str2treeHelper(s, idx, n);
    	  } else {
    		root->right = str2treeHelper(s, idx, n);
    	  }
    	} else if (s[idx] == ')') {
    	  idx++;
    	  return root;
    	}
      }
      
      return root;
    }
    
    TreeNode* str2tree(string s) {
      int n = s.size();
      if (n < 1) {
    	return nullptr;
      }
      
      int idx = 0;
      
      return str2treeHelper(s, idx, n);
    }
    
    
    TreeNode* str2tree(string s) {
      int n = s.size();
      if (n < 1) {
    	return nullptr;
      }
      
      int i = 0;
      stack<pair<TreeNode*, int>> stk;
      
      while (i < n) {
    	if (s[i] == '-' || isdigit(s[i])) {
    	  int neg = 1;
    	  if (s[i] == '-') {
    		neg = -1;
    		i++;
    	  }
    	  int sum = 0;
    	  while (i < n && isdigit(s[i])) {
    		sum = sum * 10 + s[i] - '0';
    		i++;
    	  }
    	  sum *= neg;
    	  stk.push(make_pair(new TreeNode(sum), 0));
    	} else if (s[i] == ')') {
    	  if (s[i - 1] == '(') {
    		stk.top().second++;
    		i++;
    		continue;
    	  }
    	  auto top = stk.top();
    	  stk.pop();
    	  auto& p = stk.top();
    	  if (p.second == 0) {
    		p.first->left = top.first;
    	  } else {
    		p.first->right = top.first;
    	  }
    	  p.second++;
    	  i++;
    	} else {
    	  i++;
    	}
      }
      
      return stk.top().first;
    }
    

Log in to reply
 

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