536. Construct Binary Tree from String

O(n) time

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* str2tree(string s) {
        s += '(';
        TreeNode dummy;
        stack<TreeNode *> stk{{&dummy}};
        for (int i = 0, j = 0, n = s.length(); i < n; ++i) {
            if (s[i] != '(' && s[i] != ')') continue;
            if (i > j) {
                auto x = new TreeNode(stoi(s.substr(j, i - j)));// 把i和j两个相邻括号之间的内容变成数
                if (stk.top()->left) {
                    stk.top()->right = x;
                } else {
                    stk.top()->left = x;
                }
                stk.push(x);
            }
            if (s[i] == ')') {
                stk.pop();
            }
            j = i + 1;
        }
        return dummy.left;
    }
};

/**
 * 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) {
        s += '('; // in case no parenthesis
        stack<TreeNode*> stk;
        TreeNode dummy_root(0);
        stk.push(&dummy_root);
        for (int b = 0, i = s.find_first_of("()"); i != string::npos; b = i + 1, i = s.find_first_of("()", b)) { // find_first_of search any match of the input chars
            TreeNode *x = nullptr;
            string num = s.substr(b, i - b);
            if (!num.empty()) { // num might be empty e.g. ))
                x = new TreeNode(stoi(num));
            }
            if (!stk.top()->left) {
                stk.top()->left = x;
            } else if (!stk.top()->right) { // must use else if to check right child to avoid overwrite e.g. 4(2(3)(1)), 3 and 1 are 2's children, )) creates a nullptr to try overwriting 1
                stk.top()->right = x;
            }
            if (x) {
                stk.push(x);
            }
            if (s[i] == ')') {
                stk.pop();
            }
        }
        return dummy_root.left;
    }
};

/**
 * 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) {
        stack<TreeNode*> stk;
        TreeNode dummy_root(0);
        stk.push(&dummy_root);
        string num;
        for (int n = s.length(), i = 0; i < n; ++i) {
            if (s[i] == '(') continue; // 可有可无
            while (i < n && (isdigit(s[i]) || s[i] == '-')) {
                num += s[i++];
            }
            TreeNode *x = nullptr;
            if (!num.empty()) {
                x = new TreeNode(stoi(num));
                --i;
                num.clear();
            }
            if (!stk.top()->left) {
                stk.top()->left = x;
            } else if (!stk.top()->right) {
                stk.top()->right = x;
            }
            if (x) {
                stk.push(x);
            }
            if (s[i] == ')') {
                stk.pop();
            }
        }
        return dummy_root.left;
    }
};