05 August 2008
从字符串中恢复二叉树，数字代表结点，括号代表深度
例如
Input: s = “4(2(3)(1))(6(5))”
Output: [4,2,6,3,1,5]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public TreeNode str2tree(String s) {
//Recursive
if (s == null || s.length() == 0) {
return null;
}
int firstParen = s.indexOf("(");
int val = firstParen == -1 ? Integer.parseInt(s) : Integer.parseInt(s.substring(0, firstParen));
TreeNode cur = new TreeNode(val);
if (firstParen == -1) {
return cur;
}
int start = firstParen, leftParenCount = 0;
for (int i = start; i < s.length(); i++) {
if (s.charAt(i) == '(') {
leftParenCount++;
} else if (s.charAt(i) == ')') {
leftParenCount--;
}
if (leftParenCount == 0 && start == firstParen) {
cur.left = str2tree(s.substring(start + 1, i));
start = i + 1;
} else if (leftParenCount == 0) {
cur.right = str2tree(s.substring(start + 1, i));
}
}
return cur;
}
}