536. Construct Binary Tree from String

Explanation:

Given a string representing a binary tree, we need to construct the binary tree from this string.

We can solve this problem using a recursive approach. We will start by parsing the string to extract the root value and construct the root node. Then, we will recursively construct the left and right subtrees by identifying their respective strings from the input string.

Example:

Input: "4(2(3)(1))(6(5))" Output: A binary tree representing the input string.

Algorithm:

Start by creating a helper function that takes a string and a start index as input.
Extract the root value from the string at the start index.
Create the root node with the extracted value.
Check if there are left and right children for the current node.
If there is a left child, recursively call the helper function with the substring representing the left child.
If there is a right child, recursively call the helper function with the substring representing the right child.
Return the constructed root node.
Finally, call the helper function with the input string starting from index 0.

Time Complexity:

The time complexity of this approach is O(n), where n is the length of the input string, as we traverse the string only once.

Space Complexity:

The space complexity is also O(n) due to the recursive calls and the space used by the call stack.

:

View Leetcode Problem

class Solution {
    public TreeNode str2tree(String s) {
        if (s.isEmpty()) {
            return null;
        }
        return helper(s, 0);
    }
    
    private TreeNode helper(String s, int start) {
        int end = start;
        while (end < s.length() && (Character.isDigit(s.charAt(end)) || s.charAt(end) == '-')) {
            end++;
        }
        
        TreeNode root = new TreeNode(Integer.parseInt(s.substring(start, end)));
        
        if (end < s.length() && s.charAt(end) == '(') {
            int count = 1;
            int i = end + 1;
            while (count != 0) {
                if (s.charAt(i) == '(') {
                    count++;
                } else if (s.charAt(i) == ')') {
                    count--;
                }
                i++;
            }
            root.left = helper(s, end + 1);
            root.right = helper(s, i);
        }
        
        return root;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.