Simple C++ stack solution using TreeNode**


  • 0
    H
    class Solution {
    public:
        TreeNode* str2tree(string s) {
            if (!s.size()) return nullptr;
            stack<TreeNode*> stk;
            TreeNode* root;
            TreeNode** cur = &root;
            for (int i = 0; i < s.size(); ++i) {
                if (s[i] == '(') {
                    if (s[i-1] == ')') cur = &(stk.top()->right);
                    else cur = &(stk.top()->left);
                } else if (s[i] == ')') {
                    if (s[i-1] != '(') stk.pop();
                } else {
                    stk.push(*cur = new TreeNode(getNum(i , s)));
                }
            }
            return root;
        }
    private:
        inline int getNum(int &i , const string &s) {
            int num = 0, sgn = 1;
            for (; i < s.size(); ++i) {
                if (s[i] == '(' || s[i] == ')') break;
                if (s[i] == '-') sgn = -1;
                else num = num * 10 + s[i] - '0';
            }
            --i;
            return (sgn == 1) ? num : -num;
        }
    };
    

Log in to reply
 

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