536. Construct Binary Tree from String

Description

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.

Constraints

• 0 <= s.length <= 3 * 104

• s consists of digits, '(', ')', and '-' only.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

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]

Solutions

TreeNode

// Definition for a binary tree node.
public class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	
	TreeNode() {}
	
	TreeNode(int val) { 
		this.val = val;
	}
	
	TreeNode(int val, TreeNode left, TreeNode right) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private int i = 0;
    
    public TreeNode str2tree(String s) {
        if(s == null || s.trim().length() == 0) {
            return null;
        }
        return str2treeHelper(s);
    }
    
    private TreeNode str2treeHelper(String s) {
        TreeNode root = null;
        if(s.charAt(i) != '(') {
            root = new TreeNode(getIntVal(s));
        }
        
        TreeNode leftNode = null, rightNode = null;
        
        if(i < s.length() && s.charAt(i) == '(') {
            i++;
            leftNode = str2treeHelper(s);
        }
        if(i < s.length() && s.charAt(i) == '(') {
            i++;
            rightNode = str2treeHelper(s);
        }
        
        root.left = leftNode;
        root.right = rightNode;
        i++;
        return root;
    }
    
    private int getIntVal(String s) {
        StringBuilder sb = new StringBuilder();
        while(i < s.length()) {
            if(s.charAt(i) == '(' || s.charAt(i) == ')') {
                break;
            }
            sb.append(s.charAt(i));
            i++;
        }
        return Integer.valueOf(sb.toString());
    }
}

Follow up