Skip to content

536. Construct Binary Tree from String 👍

Approach 1: Recursive

  • Time: $(n)$
  • Space: $O(h)$
 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
class Solution {
 public:
  TreeNode* str2tree(string s) {
    if (s.empty())
      return nullptr;
    int i = 0;
    return str2tree(s, i);
  }

 private:
  TreeNode* str2tree(const string& s, int& i) {
    const int start = i;  // the start index of `val`
    if (s[i] == '-')
      ++i;
    while (i < s.length() && isdigit(s[i]))
      ++i;

    const int val = stoi(s.substr(start, i - start));
    TreeNode* root = new TreeNode(val);

    // the left child
    if (i < s.length() && s[i] == '(') {
      ++i;  // '('
      root->left = str2tree(s, i);
      ++i;  // ')'
    }

    // the right child
    if (i < s.length() && s[i] == '(') {
      ++i;  // '('
      root->right = str2tree(s, i);
      ++i;  // ')'
    }

    return root;
  }
};

 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
class Solution {
  public TreeNode str2tree(String s) {
    if (s.isEmpty())
      return null;
    return helper(s);
  }

  private int i = 0;

  private TreeNode helper(final String s) {
    final int start = i; // the start index of `val`
    if (s.charAt(i) == '-')
      ++i;
    while (i < s.length() && Character.isDigit(s.charAt(i)))
      ++i;

    final int val = Integer.parseInt(s.substring(start, i));
    TreeNode root = new TreeNode(val);

    // the left child
    if (i < s.length() && s.charAt(i) == '(') {
      ++i; // '('
      root.left = helper(s);
      ++i; // ')'
    }

    // the right child
    if (i < s.length() && s.charAt(i) == '(') {
      ++i; // '('
      root.right = helper(s);
      ++i; // ')'
    }

    return root;
  }
}

Approach 2: Iterative

  • Time: $(n)$
  • Space: $O(h)$
 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
class Solution {
 public:
  TreeNode* str2tree(string s) {
    if (s.empty())
      return nullptr;

    stack<TreeNode*> stack;

    for (int l = 0, r = 0; r < s.length(); l = ++r)
      if (s[r] == ')') {
        stack.pop();
      } else if (isdigit(s[r]) || s[r] == '-') {
        while (r + 1 < s.length() && isdigit(s[r + 1]))
          ++r;
        const int val = stoi(s.substr(l, r - l + 1));
        TreeNode* node = new TreeNode(val);
        if (!stack.empty()) {
          TreeNode* parent = stack.top();
          if (parent->left)
            parent->right = node;
          else
            parent->left = node;
        }
        stack.push(node);
      }

    return stack.top();
  }
};

 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
class Solution {
  public TreeNode str2tree(String s) {
    if (s.isEmpty())
      return null;

    Deque<TreeNode> stack = new ArrayDeque<>();

    for (int l = 0, r = 0; r < s.length(); l = ++r)
      if (s.charAt(r) == ')') {
        stack.pop();
      } else if (Character.isDigit(s.charAt(r)) || s.charAt(r) == '-') {
        while (r + 1 < s.length() && Character.isDigit(s.charAt(r + 1)))
          ++r;
        final int val = Integer.parseInt(s.substring(l, r + 1));
        TreeNode node = new TreeNode(val);
        if (!stack.isEmpty()) {
          TreeNode parent = stack.peek();
          if (parent.left != null)
            parent.right = node;
          else
            parent.left = node;
        }
        stack.push(node);
      }

    return stack.peek();
  }
}