[536. Construct Binary Tree from String] #leetcode

536_0902.java

class Solution {
  // O(n^2) O(n)
    public TreeNode str2tree(String s) {
        if (s.equals("")) return null;
        
        int i = s.indexOf("(");
        if (i == -1) {
            TreeNode node = new TreeNode(Integer.parseInt(s));
            return node;
        }
        
        TreeNode node = new TreeNode(Integer.parseInt(s.substring(0, i)));
        
        String c = s.substring(i);
        int idx = getChildren(c);
        System.out.println(c);
        System.out.println(idx);
        
        node.left = str2tree(1 < idx - 1? c.substring(1, idx-1) : "");
        node.right = str2tree(idx+1 < c.length()-1? c.substring(idx+1, c.length()-1) : "");
        
        return node;
    }
    
    private Integer getChildren(String s) {
        Deque<String> stack = new LinkedList<String>();
        int i;
        for (i = 0; i < s.length(); i++) {
            String c = s.substring(i, i+1);
            if (c.equals("(")) stack.add(c);
            if (c.equals(")")) stack.removeLast();
            if (stack.isEmpty()) return i+1;
        }
        
        return i+1;
    }
    
}

public class Solution {
    public TreeNode str2tree(String s) {
        // Base case
        if (s.length() == 0) return null;
        
        // Create root
        int i = 0, j = 0;
        while (j < s.length() && (Character.isDigit(s.charAt(j)) || s.charAt(j) == '-')) j++;
        TreeNode root = new TreeNode(Integer.parseInt(s.substring(i, j)));
        
        // Left child
        if (j < s.length()) {
            i = j;
            int count = 1;
            while (j + 1 < s.length() && count != 0) {
                j++;
                if (s.charAt(j) == ')') count--;
                if (s.charAt(j) == '(') count++;
            }
            root.left = str2tree(s.substring(i + 1, j));
        }
        
        j++;
        // Right child
        if (j < s.length()) {
            root.right = str2tree(s.substring(j + 1, s.length() - 1));
        }
        
        return root;
    }
}