You need to construct a binary tree from a string consisting of parenthesis and integers.The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root’s value and a pair of parenthesis contains a child binary tree with the same structure.You always start to construct the left child node of the parent first if it exists.
from leetcode_py import TreeNodeclass Solution: # Time: O(n) # Space: O(h) for the recursion stack, where h is the tree height def str2tree(self, s: str) -> TreeNode[int] | None: if not s: return None def parse(i: int) -> tuple[TreeNode[int], int]: 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] == "(": node.left, i = parse(i + 1) i += 1 # closing paren of the left subtree if i < len(s) and s[i] == "(": node.right, i = parse(i + 1) i += 1 # closing paren of the right subtree return node, i root, _ = parse(0) return root
