536. Construct Binary Tree from String

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
/*
Recursive Solution (This solution makes sure the recursion starts at the value.)
This solution takes care of "()" (left child is null).

Time Complexity: O(N)
Space Complexity: O(H)
N = Length of the input string
H = Height of the output tree.
*/
class Solution {
    public TreeNode str2tree(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }
        return str2treeHelper(s, new int[1]);
    }

    private TreeNode str2treeHelper(String s, int[] index) {
        if (index[0] >= s.length()) {
            return null;
        }

        int start = index[0];
        while (index[0] < s.length() && s.charAt(index[0]) != '(' && s.charAt(index[0]) != ')') {
            index[0]++;
        }

        TreeNode node = new TreeNode(Integer.parseInt(s.substring(start, index[0])));

        if (index[0] < s.length() && s.charAt(index[0]) == '(') {
            index[0]++;
            node.left = str2treeHelper(s, index);
            if (index[0] < s.length() && s.charAt(index[0]) == '(') {
                index[0]++;
                node.right = str2treeHelper(s, index);
            }
        }

        index[0]++;
        return node;
    }
}


/*
Recursive Solution (Adding padding to the string. Making sure the recursion always start at open bracket)
This solution takes care of "()" (left child is null).

Time Complexity: O(N)
Space Complexity: O(H)
N = Length of the input string
H = Height of the output tree.
*/
class Solution {
    public TreeNode str2tree(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }
        return str2treeHelper("(" + s + ")", new int[1]);
    }

    private TreeNode str2treeHelper(String s, int[] index) {
        int start = index[0]+1;
        int end = start+1;
        while (end < s.length() && Character.isDigit(s.charAt(end))) {
            end++;
        }
        index[0] = end;

        TreeNode node = new TreeNode(Integer.parseInt(s.substring(start, end)));

        if (s.charAt(index[0]) == '(') {
            node.left = str2treeHelper(s, index);
            if (s.charAt(index[0]) == '(') {
                node.right = str2treeHelper(s, index);
            }
        }

        index[0]++;
        return node;
    }
}


/*
Iterative Solution
This solution constructs the left child node of the parent first if it exists

Time Complexity: O(N)
Space Complexity: O(H)
N = Length of the input string
H = Height of the output tree.
*/
class Solution {
    public TreeNode str2tree(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }

        Stack<TreeNode> stack = new Stack();
        int i = 0;
        while (i < s.length()) {
            if (s.charAt(i) == ')' && !stack.isEmpty()) {
                stack.pop();
                i++;
                continue;
            }
            if (s.charAt(i) == '(') {
                i++;
            }
            int start = i;
            while(i < s.length() && (s.charAt(i) == '-' || Character.isDigit(s.charAt(i)))) {
                i++;
            }
            TreeNode node = new TreeNode(Integer.parseInt(s.substring(start, i)));
            if (!stack.isEmpty()) {
                TreeNode parent = stack.peek();
                if (parent.left == null) {
                    parent.left = node;
                } else {
                    parent.right = node;
                }
            }
            stack.push(node);
        }

        return stack.isEmpty() ? null : stack.peek();
    }
}