Problem Statement
In this problem, you are given a string that describes the structure of a binary tree. The string includes integers and pairs of parentheses. Each integer in the string represents a node's value in the tree, and the pairs of parentheses that follow an integer may contain further details representing the node's left and/or right children using the same format.
Your task is to interpret this string and construct the corresponding binary tree. Each node in the tree can potentially have two children (left and right), and the construction of children adheres strictly to the order given in the string: first the left child if present within the first parentheses, then the right within the next pair if present. The challenge primarily involves parsing nested structures encoded in the string and appropriately building the binary tree based on this encoded format.
Examples
Example 1
Input:
s = "4(2(3)(1))(6(5))"
Output:
[4,2,6,3,1,5]
Example 2
Input:
s = "4(2(3)(1))(6(5)(7))"
Output:
[4,2,6,3,1,5,7]
Example 3
Input:
s = "-4(2(3)(1))(6(5)(7))"
Output:
[-4,2,6,3,1,5,7]
Constraints
0 <= s.length <= 3 * 104sconsists of digits,'(',')', and'-'only.- All numbers in the tree have value at most than
230.
Approach and Intuition
To tackle the problem of constructing a binary tree from a string representation that includes parenthesis and integers, one must understand the structured format used:
- Every integer represents the root value of a subtree.
- A pair of parentheses following an integer describes the subtree rooted at the current node. The first pair, if present, always describes the left child. The subsequent pair, likewise, describes the right child.
Given the recursive nature of the tree's definition within the string (i.e., a node followed potentially by descriptions of its children, also in the form of node plus children), a recursive or stack-based parsing method can be naturally fitting for this problem.
- For each node:
- Identify the integer that represents the node's value.
- Look for a pair of parentheses immediately following the integer. If it exists, it defines the left subtree.
- Check for another pair of parentheses immediately after. This would define the right subtree.
- Recurse or iterate into each pair of parentheses to construct the respective subtrees.
This recursive parsing mirrors the recursive structure of the tree itself, making it an intuitive approach. Handling digits (including negatives), and correctly identifying and separating left and right subtrees encapsulated within nested parentheses are key challenges here.
The constraints guide the solution's efficiency requirements, emphasizing the need for handling reasonably large strings effectively while adhering to the defined tree construction rules.
Solutions
- Java
- Python
class Solution {
public TreeNode stringToTree(String input) {
if (input.isEmpty()) {
return null;
}
TreeNode rootNode = new TreeNode();
Stack<TreeNode> nodeStack = new Stack<TreeNode>();
nodeStack.push(rootNode);
for (int pos = 0; pos < input.length();) {
TreeNode currentNode = nodeStack.pop();
// Processing node value
if (Character.isDigit(input.charAt(pos)) || input.charAt(pos) == '-') {
Pair<Integer, Integer> valueData = extractNumber(input, pos);
int number = valueData.getKey();
pos = valueData.getValue();
currentNode.val = number;
// Check for children starting with the left child
if (pos < input.length() && input.charAt(pos) == '(') {
nodeStack.push(currentNode);
currentNode.left = new TreeNode();
nodeStack.push(currentNode.left);
}
} else if (input.charAt(pos) == '(' && currentNode.left != null) { // Left child already created
nodeStack.push(currentNode);
currentNode.right = new TreeNode();
nodeStack.push(currentNode.right);
}
++pos;
}
return nodeStack.isEmpty() ? rootNode : nodeStack.pop();
}
public Pair<Integer, Integer> extractNumber(String input, int start) {
boolean negative = false;
// Checking for negative values
if (input.charAt(start) == '-') {
negative = true;
start++;
}
int value = 0;
while (start < input.length() && Character.isDigit(input.charAt(start))) {
value = value * 10 + (input.charAt(start) - '0');
start++;
}
return new Pair<Integer, Integer>(negative ? -value : value, start);
}
}
Constructing a binary tree from a string representation involves careful parsing and node management. The provided Java solution achieves this by utilizing a stack data structure to hold and manage tree nodes as they are traversed:
- Initialize an empty stack to keep track of tree nodes during the construction process.
- Create a root node and push it onto the stack immediately.
- Iterate through the characters in the input string:
- If encountering a digit or a '-' for a negative number, determine the entire number and set the current node's value.
- Decide if the current section represents the left or the right child of a node based on parentheses surrounding the digits.
- If it's a left child, create a new node for it and push it onto the stack for later processing.
- If the left child has already been accounted for and a '(' is encountered, the next node process is a right child.
- For every node processed, pop from the stack once complete move to the next node.
- Ensure node connections are maintained as each new node is created and positioned as either a left or right child.
Finally, after processing the whole string, the constructed binary tree based on the string representation is returned. The method leverages a helper function extractNumber to parse out integers from the string, which are then used to set node values correctly, handling both positive and negative numbers.
class Solution:
def string_to_tree(self, input_string: str) -> TreeNode:
if not input_string:
return None
initial_node = TreeNode()
node_stack = [initial_node]
pos = 0
while pos < len(input_string):
current_node = node_stack.pop()
if input_string[pos].isdigit() or input_string[pos] == '-':
value, pos = self._parse_integer(input_string, pos)
current_node.val = value
if pos < len(input_string) and input_string[pos] == '(':
node_stack.append(current_node)
current_node.left = TreeNode()
node_stack.append(current_node.left)
elif current_node.left and input_string[pos] == '(':
node_stack.append(current_node)
current_node.right = TreeNode()
node_stack.append(current_node.right)
pos += 1
return node_stack.pop() if node_stack else initial_node
def _parse_integer(self, input_string: str, index: int) -> (int, int):
negative_flag = False
if input_string[index] == '-':
negative_flag = True
index += 1
digit_accumulator = 0
while index < len(input_string) and input_string[index].isdigit():
digit_accumulator = digit_accumulator * 10 + int(input_string[index])
index += 1
return -digit_accumulator if negative_flag else digit_accumulator, index
In the Python solution provided, the goal is to construct a binary tree from a string representation. The implementation uses a class named Solution containing two methods: string_to_tree and a private method _parse_integer.
The method string_to_tree initializes by checking if the input string is empty and returns None if true. It creates an initial tree node and uses a stack for managing tree nodes during tree construction. The function parses the string character by character:
- When a digit or a '-' is encountered,
_parse_integeris called to extract the number and update the position index. - If an opening parenthesis follows, it implies the presence of a child node. A new TreeNode is created, and processing continues for the next characters to determine if the node is a left or a right child.
- The method ensures handling of both left and right children of the current node before moving further in the string.
The tree is constructed by repeatedly popping and initializing new nodes until the end of the string is reached, returning the last node unless the stack is empty, in which case the initial node is returned.
In _parse_integer, the method processes characters to form an integer from the current index forward, accounting also for negative numbers. After accumulating the digits, it returns the formed integer and the new position index in the tuple, which allows the string_to_tree method to continue parsing from the correct position.
This approach cleverly uses a stack to manage backward traversal through the string and employs robust handling for nested structures indicated by parentheses, typical in serialized tree representations. By returning tree nodes in a structured manner as predetermined by the input string, it represents a solution capable of deserializing a string into a tree data structure efficiently and reliably.
No comments yet.