C++ O(n) One Pass Recursive Solution


  • 0
    F
    class Solution {
        pair<TreeNode *, int> construct(string const & s, int cur)
        {
            if (cur == s.size())
                return {nullptr, cur};
            int sign = 1;
            if (s[cur] == '-')
            {
                cur ++;
                sign = -1;
            }
            int n = 0;
            while(cur < s.size() && isdigit(s[cur]))
            {
                n = n*10 + s[cur] - '0';
                cur ++;
            }
            n *= sign;
            TreeNode * node = new TreeNode(n);
            if (cur == s.size() || s[cur] == ')')
                return {node, cur + 1};
            if (s[cur] == '(')
            {
                auto res = construct(s, cur + 1);
                node->left = res.first;
                cur = res.second;
            }
            if (cur == s.size() || s[cur] == ')')
                return {node, cur + 1};
            if (s[cur] == '(')
            {
                auto res = construct(s, cur + 1);
                node->right = res.first;
                cur = res.second;
            }
            return {node, cur + 1};
        }
    public:
        TreeNode* str2tree(string const & s) {
            return construct(s, 0).first;
        }
    };
    

Log in to reply
 

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