Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

536. Construct Binary Tree from String

Time: $(n)$

Space: $O(h)$

			


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;  // 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);

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

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

    return root;
  }
};




			


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; // 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);

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

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

    return root;
  }
}




			


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();
  }
};