Skip to content

1028. Recover a Tree From Preorder Traversal 👍

  • Time: $O(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* 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;
  }
};
 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 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;
  }
}