The Leetcode problem "Construct Binary Tree from String" asks you to construct a binary tree from a string consisting of integers and parentheses. The string represents a preorder traversal of a binary tree, where:
(...) enclose the left and right subtrees."4(2(3)(1))(6(5))", you should build the following binary tree:
4
/ \
2 6
/ \ /
3 1 5
At first glance, the problem resembles parsing a mathematical expression. Each number is a node, and each pair of parentheses indicates a subtree. A brute-force approach might involve recursively splitting the string at every parenthesis, but this quickly becomes messy due to nested structures.
To optimize, we can recognize that the string is a preorder traversal, and the parentheses always wrap the left and right children, in order. This suggests a recursive or stack-based parsing approach, where we process numbers and recursively parse their children as we encounter parentheses.
The main challenge is handling nested parentheses and multi-digit (or negative) numbers. We need to carefully keep track of our current position in the string and be able to parse out each subtree correctly.
We can solve the problem using a recursive parsing strategy. Here’s how:
This approach is efficient because it processes each character in the string exactly once, and never splits or copies substrings unnecessarily.
Let's walk through the input "4(2(3)(1))(6(5))":
4 as the root node.2 as left child of 4.3 as left child of 2. No more children, return node 3.1 as right child of 2. No more children, return node 1.6 as right child of 4.5 as left child of 6. No more children, return node 5.
Brute-force Approach: If we tried to split substrings at every parenthesis, each split operation would take O(n) time, leading to an overall complexity worse than O(n2).
Optimized Recursive Parsing: Our approach visits each character in the string exactly once, so the time complexity is O(n), where n is the length of the input string.
Space complexity is also O(n), due to the recursion stack and the space needed to store the binary tree nodes.
To solve "Construct Binary Tree from String", we leverage the preorder traversal structure and use a recursive parser that walks through the string character by character. This avoids inefficient substring operations and handles nested expressions cleanly. The result is an elegant, linear-time solution that builds the binary tree as we parse, with each node and subtree constructed at exactly the right moment.
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def str2tree(self, s: str) -> TreeNode:
if not s:
return None
def helper(index):
if index >= len(s):
return None, index
# Parse the integer value (may be negative and multi-digit)
sign = 1
if s[index] == '-':
sign = -1
index += 1
num = 0
while index < len(s) and s[index].isdigit():
num = num * 10 + int(s[index])
index += 1
node = TreeNode(sign * num)
# Parse left child if '('
if index < len(s) and s[index] == '(':
index += 1 # skip '('
node.left, index = helper(index)
index += 1 # skip ')'
# Parse right child if '('
if index < len(s) and s[index] == '(':
index += 1 # skip '('
node.right, index = helper(index)
index += 1 # skip ')'
return node, index
root, _ = helper(0)
return root
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* str2tree(string s) {
int idx = 0;
return helper(s, idx);
}
TreeNode* helper(const string& s, int& idx) {
if (idx >= s.size()) return nullptr;
// Parse value (may be negative)
int sign = 1;
if (s[idx] == '-') {
sign = -1;
idx++;
}
int num = 0;
while (idx < s.size() && isdigit(s[idx])) {
num = num * 10 + (s[idx] - '0');
idx++;
}
TreeNode* node = new TreeNode(sign * num);
// Parse left child
if (idx < s.size() && s[idx] == '(') {
idx++; // skip '('
node->left = helper(s, idx);
idx++; // skip ')'
}
// Parse right child
if (idx < s.size() && s[idx] == '(') {
idx++; // skip '('
node->right = helper(s, idx);
idx++; // skip ')'
}
return node;
}
};/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode str2tree(String s) {
if (s == null || s.length() == 0) return null;
int[] idx = new int[1];
return helper(s, idx);
}
private TreeNode helper(String s, int[] idx) {
if (idx[0] >= s.length()) return null;
// Parse value (may be negative)
int sign = 1;
if (s.charAt(idx[0]) == '-') {
sign = -1;
idx[0]++;
}
int num = 0;
while (idx[0] < s.length() && Character.isDigit(s.charAt(idx[0]))) {
num = num * 10 + (s.charAt(idx[0]) - '0');
idx[0]++;
}
TreeNode node = new TreeNode(sign * num);
// Parse left child
if (idx[0] < s.length() && s.charAt(idx[0]) == '(') {
idx[0]++; // skip '('
node.left = helper(s, idx);
idx[0]++; // skip ')'
}
// Parse right child
if (idx[0] < s.length() && s.charAt(idx[0]) == '(') {
idx[0]++; // skip '('
node.right = helper(s, idx);
idx[0]++; // skip ')'
}
return node;
}
}
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {string} s
* @return {TreeNode}
*/
var str2tree = function(s) {
if (!s || s.length === 0) return null;
let i = 0;
function helper() {
if (i >= s.length) return null;
// Parse value (may be negative)
let sign = 1;
if (s[i] === '-') {
sign = -1;
i++;
}
let num = 0;
while (i < s.length && s[i] >= '0' && s[i] <= '9') {
num = num * 10 + (s[i].charCodeAt(0) - '0'.charCodeAt(0));
i++;
}
let node = new TreeNode(sign * num);
// Parse left child
if (i < s.length && s[i] === '(') {
i++; // skip '('
node.left = helper();
i++; // skip ')'
}
// Parse right child
if (i < s.length && s[i] === '(') {
i++; // skip '('
node.right = helper();
i++; // skip ')'
}
return node;
}
return helper();
};