# 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)