536. Construct Binary Tree from String

Posted on Edited on In

536. Construct Binary Tree from String

Description

You need to construct a binary tree from a string consisting of parenthesis and integers.

The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root’s value and a pair of parenthesis contains a child binary tree with the same structure.

You always start to construct the left child node of the parent first if it exists.

Example 1:

1
2
Input: s = "4(2(3)(1))(6(5))"
Output: [4,2,6,3,1,5]

Example 2:

1
2
Input: s = "4(2(3)(1))(6(5)(7))"
Output: [4,2,6,3,1,5,7]

Example 3:

1
2
Input: s = "-4(2(3)(1))(6(5)(7))"
Output: [-4,2,6,3,1,5,7]

Constraints:

  • 0 <= s.length <= 3 * 10^4
  • s consists of digits, '(', ')', and '-' only.

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * 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) {
        if (s.empty()) {
            return nullptr;
        }
        int start = s.find_first_of('(');
        if (start == -1)
            start = s.size();
        int val = stoi(s.substr(0, start));
        TreeNode* root = new TreeNode(val);
        if (start == s.size()) {
            return root;
        }
        int parenthesis = 0, i = 0;
        for (i = start; i < s.size(); i++) {
            if (s[i] == '(') {
                parenthesis++;
            } else if (s[i] == ')') {
                parenthesis--;
            }
            if (parenthesis == 0) {
                break;
            }
        }
        // s[start] = '(', s[i] = ')'
        root->left = str2tree(s.substr(start + 1, i - (start + 1)));
        if (i == s.size() - 1) {
            return root;
        }
        // i + 2 since we need to skip the ')' and '('
        root->right = str2tree(s.substr(i + 2, s.size() - 1 - (i + 2)));
        return root;
    }
};

With stack:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * 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) {
        if (s.empty()) {
            return nullptr;
        }

        TreeNode* root = new TreeNode();
        stack<TreeNode*> stk;
        stk.push(root);

        for (int index = 0; index < s.size(); index++) {
            TreeNode* node = stk.top();
            stk.pop();

            if (isdigit(s[index]) || s[index] == '-') {
                int sign = 1;
                if (s[index] == '-') {
                    sign = -1;
                    index++;
                }
                int cur = 0;
                while (index < s.size() && isdigit(s[index])) {
                    cur = cur * 10 + s[index] - '0';
                    index++;
                }
                cur *= sign;
                node->val = cur;
                if (index < s.size() && s[index] == '(') {
                    node->left = new TreeNode();
                    stk.push(node);
                    stk.push(node->left);
                }
            } else if (s[index] == '(' && node->left) {
                node->right = new TreeNode();
                stk.push(node);
                stk.push(node->right);
            }
        }
        return stk.empty() ? root : stk.top();
    }
};