Solution Explanation: Construct Binary Tree from String

This problem requires constructing a binary tree from a string representation. The string follows a specific format: an integer representing the root node, followed by zero, one, or two pairs of parentheses, each containing a subtree representation.

Approach

The most efficient approach is a recursive depth-first search (DFS). The function dfs recursively parses the input string s.

1. Base Case: If the string s is empty, it returns null (or None in Python).

2. Finding the Root: It finds the index p of the first opening parenthesis '('.

   • If p is not found (-1), the entire string represents a single node (leaf node). It converts the string to an integer and creates a TreeNode with that value.
   • Otherwise, the substring before p represents the root node's value. A TreeNode is created with this value.

3. Recursive Calls for Children: The code iterates through the string from p to find matching closing parentheses ')', keeping track of the parenthesis balance using cnt.

   • When cnt becomes 0, it has found a complete subtree.
   • If it's the first parenthesis encountered (start == p), it recursively calls dfs on the substring representing the left subtree and assigns it to root.left.
   • Otherwise, it's the second parenthesis, and it recursively calls dfs on the substring representing the right subtree and assigns it to root.right.

4. Return Value: The function returns the constructed TreeNode representing the current subtree.

Code Explanation (Python)

The Python code implements this recursive DFS approach concisely:

class Solution:
    def str2tree(self, s: str) -> TreeNode:
        def dfs(s):
            if not s:  # Base case: empty string
                return None
            p = s.find('(')  # Find first '('
            if p == -1:  # No parenthesis, leaf node
                return TreeNode(int(s))
            root = TreeNode(int(s[:p]))  # Create root node
            start = p
            cnt = 0
            for i in range(p, len(s)):  # Find matching ')'
                if s[i] == '(':
                    cnt += 1
                elif s[i] == ')':
                    cnt -= 1
                if cnt == 0:
                    if start == p:  # Left subtree
                        root.left = dfs(s[start + 1:i])
                        start = i + 1
                    else:  # Right subtree
                        root.right = dfs(s[start + 1:i])
            return root
 
        return dfs(s)

Time and Space Complexity

• Time Complexity: O(N), where N is the length of the input string. Each character is visited at most a constant number of times during the parsing. The recursive calls have a depth proportional to the height of the tree, which is at most N in the worst case (a skewed tree).

• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be N, but in a balanced tree, H is log₂N. Additionally, a small amount of space is used for storing the tree nodes themselves. This makes the space complexity O(N) in the worst case and O(log N) in the best case.

The other languages (Java, C++, Go) follow the same algorithm with minor syntactic differences. The complexity analysis remains the same.