版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434823
本次周赛主要分为一下4道题:
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解决问题,战斗结束。
可优化的空间:
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变量记录它的变化过程即可。