new_contents: # Time:  O(n)
  # Space: O(h)
  
  # Definition for a binary tree node.
  # class TreeNode(object):
  #     def __init__(self, x):
  #         self.val = x
  #         self.left = None
  #         self.right = None
  
  class Solution(object):
      def str2tree(self, s):
          """
          :type s: str
          :rtype: TreeNode
          """
          def str2treeHelper(s, i):
              start = i
              if s[i] == '-': i += 1
              while i < len(s) and s[i].isdigit(): i += 1
              node = TreeNode(int(s[start:i]))
              if i < len(s) and s[i] == '(':
                  i += 1
                  node.left, i = str2treeHelper(s, i)
                  i += 1
              if i < len(s) and s[i] == '(':
                  i += 1
                  node.right, i = str2treeHelper(s, i)
                  i += 1
              return node, i
  
          return str2treeHelper(s, 0)[0] if s else None
  
subject: Create construct-binary-tree-from-string.py