C++ stack solution


  • 3
    T
    class Solution {
    public:
        TreeNode* str2tree(string s) {
            stack<TreeNode*> stk;
            for (int i = 0, sz = s.size(); i < sz; ++i) {
                char ch = s[i];
                if ( ch == '(') continue;
                
                if (isdigit(ch) || ch == '-') {
                    int v = 0, sig = 1;
                    if (ch == '-') { sig = -1; ++i;}
                    while (i < sz && isdigit(s[i])) {
                        v = v * 10 + s[i++] - '0';
                    }
                    stk.emplace(new TreeNode(v*sig)); --i;
                } else { // ')'
                    TreeNode *t = stk.top(); stk.pop(); // child
                    TreeNode *p = stk.top();            // parent    
                    !p->left ? p->left = t : p->right = t;
                }
            }
            return stk.empty() ? nullptr:stk.top();
        }
    };
    

Log in to reply
 

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