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 * 104sconsists of digits,'(',')', and'-'only.
Approach
Links
GeeksforGeeks
ProgramCreek
YouTube
Examples
Input: s = "4(2(3)(1))(6(5))"
Output: [4, 2, 6, 3, 1, 5]
Input: s = "4(2(3)(1))(6(5)(7))"
Output: [4, 2, 6, 3, 1, 5, 7]
Input: s = "-4(2(3)(1))(6(5)(7))"
Output: [-4, 2, 6, 3, 1, 5, 7]
Solutions
// 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;
}
}/**
* 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
Last updated
Was this helpful?