C++ iterative using stack, looping over chars


  • 0
    L
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* str2tree(string s) {
            if (s.length()==0)
            return NULL;
            stack<TreeNode*> myst;
            
            TreeNode* cur = new TreeNode(0);
            TreeNode*  root = cur;
            myst.push(cur);
            int sign = 1;
            for (char c: s)
            {
                if (c=='(')
                {
                    TreeNode* t = new TreeNode(0);
                    if (!cur->left) cur->left = t;
                    else cur->right=t;
                    myst.push(t);
                    cur = t;
                    sign = 1;
                    continue;
                }
                if (c==')')
                {
                    myst.pop();
                    cur = myst.top();
                    continue;
                }
                if (c=='-')
                {
                    sign = -1;
                    continue;
                }            
                cur->val = sign*(abs(cur->val*10) + (c-'0'));
            }
            
            return root;
        }
    };

Log in to reply
 

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