• ㊗️
• 大家
• offer
• 多多！

## Problem

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 * 10^4
• s consists of digits, ‘(‘, ‘)’, and ‘-‘ only.

## Code

106

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

int rootEnd = s.indexOf("(");

if(rootEnd == -1){
return new TreeNode(Integer.parseInt(s));
}

int rootVal = Integer.parseInt(s.substring(0, rootEnd));

TreeNode curr = new TreeNode(rootVal);

// 第一个左括号位置
int start = rootEnd;
int leftParenCount = 0;

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

if (c == '(') {
leftParenCount++;
}else if (c == ')') {
leftParenCount--;
}

if (leftParenCount == 0) {
if(start == rootEnd) {
curr.left = str2tree(s.substring(start + 1, i));
start = i + 1;
} else {
curr.right = str2tree(s.substring(start + 1, i));
}
}
}

return curr;
}
}

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

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

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

if(c == '(') continue;

if(c == ')') {
stack.pop();
} else if(Character.isDigit(c) || c == '-'){
while(i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
i++;
}

TreeNode curr = new TreeNode(Integer.valueOf(s.substring(j, i + 1)));

if(!stack.isEmpty()){
TreeNode parent = stack.peek();
if(parent.left != null) {
parent.right = curr;
} else {
parent.left = curr;
}
}

stack.push(curr);
}
}

return stack.peek();
}
}