0536. Construct Binary Tree from String

https://leetcode.com/problems/construct-binary-tree-from-string

Description

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

Example 1:

**Input:** s = "4(2(3)(1))(6(5))"
**Output:** [4,2,6,3,1,5]

Example 2:

**Input:** s = "4(2(3)(1))(6(5)(7))"
**Output:** [4,2,6,3,1,5,7]

Example 3:

**Input:** s = "-4(2(3)(1))(6(5)(7))"
**Output:** [-4,2,6,3,1,5,7]

Constraints:

• 0 <= s.length <= 3 * 104

• s consists of digits, '(', ')', and '-' only.

ac

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int i = 0;

    public TreeNode str2tree(String s) {
        TreeNode root = null;

        int p = i;
        while (i < s.length() && s.charAt(i) != '(' && s.charAt(i) != ')') i++; // get root value
        String tmp = s.substring(p, i);
        if (tmp.length() != 0) { // some empty value like "()"
            int val = Integer.parseInt(tmp);
            root = new TreeNode(val);
        }

        if (i < s.length() && s.charAt(i++) == '(') { // '(' means the start of a child node, careful about boundary
            root.left = str2tree(s);

            if (i < s.length() && s.charAt(i++) == '(') {
                root.right = str2tree(s);
                i++; // when right child finish (not leaf), it's always like "))"
            }
        }

        return root;
    }
}

/*
regard string as a queue, similar to #297 queue deserialize
*/