Construct Binary Tree from String

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 theleftchild node of the parent first if it exists.

Example:

Input:
 "4(2(3)(1))(6(5))"

Output:
 return the tree root node representing the following tree:

       4
     /   \
    2     6
   / \   / 
  3   1 5

Note:

1. There will only be '(' , ')', ' -', '0' ~ '9', in the input string.
2. An empty tree is represented by "" instead of "()".\

Tips:

Stack:

注意怎么进栈出栈，再做一次。

Recursion:

Scan the string from left to right.

Every time we meet '(' , create left child node, then if we meet '(' again from the same parent node, we create right child node.

If every time we meet ')', just return to parent node.

Code：

Stack：

public class Solution {
    public TreeNode str2tree(String s) {
        if (s == null || s.length() == 0) return null;
        Stack<TreeNode> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (Character.isDigit(s.charAt(i)) || s.charAt(i) == '-') {
                int j = i;
                while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) i++;
                TreeNode curt = new TreeNode(Integer.valueOf(s.substring(j, i + 1)));
                if (stack.isEmpty()) stack.push(curt);
                else {
                    TreeNode parent = stack.peek();
                    if (parent.left == null) parent.left = curt;
                    else parent.right = curt;
                    stack.push(curt);
                }
            }
            if (s.charAt(i) == ')') stack.pop();
        }
        return stack.pop();
    }
}

Recursion:

public class Solution {

    int i = 0;

    public TreeNode str2tree(String s) 
    {
        if (s == null || s.length() == 0) { return null; }
        return helper(s.toCharArray());
    }

    private TreeNode helper(char[] s)
    {
        // done
        if (i == s.length) { return null; }

        // extract number
        StringBuilder num = new StringBuilder();
        while (i < s.length && s[i] != '(' && s[i] != ')') { num.append(s[i]); i++; }

        // create new node
        TreeNode n = null;
        if (num.length() != 0)
        {
            n = new TreeNode(Integer.parseInt(num.toString()));
        }
        // check parenthesis type
        if (i < s.length && s[i] == '(')
        {
            // create left child node
            i++;
            n.left = helper(s);
            i++;

            if (i < s.length && s[i] == '(')
            {
                // create right child node
                i++;
                n.right = helper(s);
                i++;
            }
        }
        // if meets ')', return to parent node
        return n;
    }
}