536. Construct Binary Tree from String
Last updated
Last updated
// 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());
}
}