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
class Solution {
 public:
  TreeNode* recoverFromPreorder(string traversal) {
    int i = 0;
    return recoverFromPreorder(traversal, 0, i);
  }

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

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

    return new TreeNode(stoi(traversal.substr(start, i - start)),
                        recoverFromPreorder(traversal, depth + 1, i),
                        recoverFromPreorder(traversal, depth + 1, i));
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public TreeNode recoverFromPreorder(String traversal) {
    return recoverFromPreorder(traversal, 0);
  }

  private int i = 0;

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

    i += depth;
    final int start = i;
    while (i < traversal.length() && Character.isDigit(traversal.charAt(i)))
      ++i;

    return new TreeNode(Integer.valueOf(traversal.substring(start, i)),
                        recoverFromPreorder(traversal, depth + 1),
                        recoverFromPreorder(traversal, depth + 1));
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:
    i = 0

    def recoverFromPreorder(depth: int) -> Optional[TreeNode]:
      nonlocal i
      nDashes = 0
      while i + nDashes < len(traversal) and traversal[i + nDashes] == '-':
        nDashes += 1
      if nDashes != depth:
        return None

      i += depth
      start = i
      while i < len(traversal) and traversal[i].isdigit():
        i += 1

      return TreeNode(int(traversal[start:i]),
                      recoverFromPreorder(depth + 1),
                      recoverFromPreorder(depth + 1))

    return recoverFromPreorder(0)