536 Construct Binary Tree from String

536. Construct Binary Tree from String

1. Question

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'(',')','-'and'0'~'9'in the input string.

2. An empty tree is represented by""instead of"()".

2. Implementation

(1) Recursion

class Solution {
    int i;
    public TreeNode str2tree(String s) {
        i = 0;
        return buildTree(s);
    }

    public TreeNode buildTree(String s) {
        StringBuilder num = new StringBuilder();

        while (i < s.length() && (s.charAt(i) == '-' || Character.isDigit(s.charAt(i)))) {
            num.append(s.charAt(i));
            i++;
        }

        if (num.length() == 0) {
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(num.toString()));

        // Left SubTree
        if (i < s.length() && s.charAt(i) == '(') {
            // Skip '('
            ++i;
            root.left = buildTree(s);
            // Skip ')'
            ++i;
        }

        // Right SubTree
        if (i < s.length() && s.charAt(i) == '(') {
            ++i;
            root.right = buildTree(s);
            ++i;
        }
        return root;
    }
}

(2) Iteration

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

        Stack<TreeNode> stack = new Stack<>();

        for (int end = 0, start = 0; end < s.length(); end++, start = end) {
            char c = s.charAt(end);

            if (c == '(') {
                continue;
            }
            else if (c == ')') {
                stack.pop();
            }
            else {
                while (end + 1< s.length() && Character.isDigit(s.charAt(end + 1))) {
                    ++end;
                }
                TreeNode curNode = new TreeNode(Integer.parseInt(s.substring(start, end + 1)));

                if (!stack.isEmpty()) {
                    TreeNode parentNode = stack.peek();
                    if (parentNode.left != null) {
                        parentNode.right = curNode;
                    }
                    else {
                        parentNode.left = curNode;
                    }
                }
                stack.push(curNode);
            }
        }
        return stack.isEmpty() ? null : stack.peek();
    }
}

3. Time & Space Complexity

Recursion: 时间复杂度O(n), 空间复杂度O(n)

Iteration: 时间复杂度O(n), 空间复杂度O(n)