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

LeetCode Solutions

1028. Recover a Tree From Preorder Traversal

Time: $O(n)$

Space: $O(h)$

			


class Solution {
 public:
  TreeNode* recoverFromPreorder(string S) {
    int i = 0;
    return recoverFromPreorder(S, 0, i);
  }

 private:
  TreeNode* recoverFromPreorder(const string& S, int depth, int& i) {
    int nDashes = 0;
    while (i + nDashes < S.length() && S[i + nDashes] == '-')
      ++nDashes;
    if (nDashes != depth)
      return nullptr;

    i += depth;
    const int start = i;
    while (i < S.length() && isdigit(S[i]))
      ++i;

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

    root->left = recoverFromPreorder(S, depth + 1, i);
    root->right = recoverFromPreorder(S, depth + 1, i);

    return root;
  }
};




			


class Solution {
  public TreeNode recoverFromPreorder(String S) {
    return recoverFromPreorder(S, 0);
  }

  private int i = 0;

  private TreeNode recoverFromPreorder(final String S, int depth) {
    int nDashes = 0;
    while (i + nDashes < S.length() && S.charAt(i + nDashes) == '-')
      ++nDashes;
    if (nDashes != depth)
      return null;

    i += depth;
    final int start = 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);

    root.left = recoverFromPreorder(S, depth + 1);
    root.right = recoverFromPreorder(S, depth + 1);

    return root;
  }
}