LeetCode Weekly Contest 23 之 536.Construct Binary Tree from String
LeetCode Weekly Contest 23 之 536.Construct Binary Tree from String
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434823
LeetCode Weekly Contest 23
赛题
本次周赛主要分为一下4道题：
- 541 Reverse String II (3分)
- 539 Minimum Time Difference (5分)
- 536 Construct Binary Tree from String (6分)
- 527 Word Abbreviation (8分)
536 Construct Binary Tree from String
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:
Note
1 There will only be ‘(‘, ‘)’, ‘-’ and ‘0’ ~ ‘9’ in the input string.
这道题是给定一个字符串，转换成对应的二叉树。在做该题时，没什么特别的想法，第一反映是递归，毕竟和树相关的题，递归操作多数。关键递归规则是什么，从Example中可以找到规律，自行理解下就好了。
怎么递归？我在本上列出了一个式子4(...)(...)，我的一个想法是，把所有的字符串分为三部分，第一部分单纯的由数字组成，第二部分，也就是第一个括号(...)，我把它命名为为leftStr，第三部分rightStr = (...)，那么我的首要目标就是，把这三部分通过某种算法给区分出来，唉，不容易啊，这操作花了我半小时！！！贴上我的代码，强行解释一波。
My first solution()
public TreeNode str2tree(String s) {
if(s.length() == 0) return null;
StringBuilder leftStr = new StringBuilder();
StringBuilder rightStr = new StringBuilder();
StringBuilder value = new StringBuilder();
/****************第一部分*****************/
for (int i = 0; i < s.length(); i++){
if(s.charAt(i)== '('){
break;
}
value.append(s.charAt(i));
}
int rootValue = Integer.parseInt(value.toString());
TreeNode root = new TreeNode(rootValue);
/****************第二部分*****************/
int f = 0,l = 0;
int isLeft = 0;
for (int i = 0; i < s.length(); i++){
if(s.charAt(i) == '('){
if(isLeft == 0)
f = i;
isLeft ++;
}
if(s.charAt(i) == ')'){
isLeft --;
if(isLeft == 0)
l = i;
}
}
for (int i = f+1; i < l; i++){
rightStr.append(s.charAt(i));
}
/****************第三部分*****************/
String tmp = s.substring(0, f);
f = 0;
l = 0;
isLeft = 0;
for (int i = 0; i < tmp.length(); i++){
if(tmp.charAt(i) == '('){
if(isLeft == 0)
f = i;
isLeft ++;
}
if(tmp.charAt(i) == ')'){
isLeft --;
if(isLeft == 0)
l = i;
}
}
for (int i = f+1; i < l; i++){
leftStr.append(s.charAt(i));
}
if(leftStr.toString().length() == 0){
leftStr = rightStr;
rightStr = null;
}
if(leftStr.length() == 0){
leftStr = null;
}
/****************第四部分*****************/
if(leftStr == null && rightStr == null) return root;
if(leftStr != null){
root.left = str2tree(leftStr.toString());
}
if(rightStr != null){
root.right = str2tree(rightStr.toString());
}
return root;
}这道题的AC率只有28%，做出来还是蛮有成就感的，但仔细看看代码，实在不美观，得使劲整顿下，先说说自己的思路吧。
对于第一部分的分离还是相当简单的，只要扫描到'('就可以跳出循环了，用个value变量记录下来即可。
关键在于如何区分后两部分，我想到的一个方法是，用一个isLeft变量来记录左括号的个数，当遇到第一个左括号时，便加加，那自然当遇到与之对应的右括号时，isLeft的值就减为0，此时，我们记录了第一个左括号的下标和与之对应的右括号的下标，自然就能subString对应的括号中的内容了。
但在写完第二部分，进行调试时发现，第二部分整出来的是rightStr的内容，所以我把这里求出来的内容给了rightStr，这里可以用subString方法，不用一个个append。既然先求出了rightStr，那我没办法，只能把第二个括号中的内容全删了，也就有了我们的第三部分。
假设存在“第一个括号的内容”，因为这是有可能不存在的，但不管三七二十一，假设存在吧，那么代码标注的第三部分内容就是用来解析leftStr，所以有了leftStr，从而把三部分都拿出来了。
当然如果只有一个括号呢？如：4(2(3)(1))，那么对于第三部分代码中的leftStr一定不会再有值了，所以直接把第一部分求出来的rightStr给leftStr就好了。
那么两个括号都没有呢？如：4，这种情况，不管是leftStr还是rightStr，它们都不会有内容，所以让它们均为null即可。
第四部分就很简单了，一个递归，如果没有左子树和右子树，则直接返回节点，如果存在左子树，把leftStr给当前节点的left。同理，存在右子树，把rightStr给当前节点的right。一个递归pre-order解决问题，战斗结束。
可优化的空间：
- 关于第一部分，当判断完’(‘后，进行跳出时，是否可以记录该下标，作为后续辅助变量？当出现其他字符时，会出大bug吧！
- 关于第二部分，直接判断完第一个左括号和右括号后直接跳出来，剩下的不就是rightStr，何必多此一举呢！没想到break，实战经验不足啊！
My second solution(39ms)
public TreeNode str2tree(String s) {
if(s.length() == 0) return null;
int val = 0;
int i = 0, k = 1;
/****************第一部分*****************/
while(i < s.length() && (s.charAt(i) >= '0' && s.charAt(i) <= '9' || s.charAt(i) == '-')){
if(s.charAt(i) == '-')
k = -1;
else
val = val * 10 + (s.charAt(i)-'0') * k;
i++;
}
TreeNode root = new TreeNode(val);
if(i == s.length()) return root;
/****************第二部分*****************/
int cnt = 0,j;
for (j = i; j < s.length();j++){
if(s.charAt(j) == '(') cnt++;
if(s.charAt(j) == ')') cnt--;
if(cnt == 0) break;
}
/****************第三部分*****************/
root.left = str2tree(s.substring(i+1, j));
if(j != s.length()-1)
root.right = str2tree(s.substring(j+2,s.length()-1));
return root;
}运行时间质的飞跃，优化了第一部分，出现指定字符才能进行计算。第二部分得到了大大的简化，当出现第一个括号的内容后，直接break，利用第一部分中的下标i和已经求出的下标j，计算leftStr。接着直接判断是否有第二个括号的内容即可，代码简化了很多！
算法细节很多，自行品味。算法逻辑很简单，就是对第一个左括号和与之对应的右括号的寻找问题，用个cnt变量记录它的变化过程即可。
腾讯云开发者
