企业站seo外包,天辰工程信息网官网,网页制作的公司网站,网站权重怎么做的2024.3.31 题目来源我的题解方法一 计数方法二 栈 题目来源
力扣每日一题#xff1b;题序#xff1a;331
我的题解
方法一 计数 当只有一个节点并且是空节点#xff0c;则表示是空树#xff0c;是一个正确的序列化正确的序列化节点数必然是偶数个#xff0c;若不是偶数… 2024.3.31 题目来源我的题解方法一 计数方法二 栈 题目来源
力扣每日一题题序331
我的题解
方法一 计数 当只有一个节点并且是空节点则表示是空树是一个正确的序列化正确的序列化节点数必然是偶数个若不是偶数个则不是一个正确的序列化除了空树起始节点必然不可能是空节点一个正确的序列化必然非空节点数量比空节点数量少1 时间复杂度O(n) 空间复杂度O(1) public boolean isValidSerialization(String preorder) {//空树if(preorder.equals(#))return true;String[] spreorder.split(,);int ns.length;//包含空节点的树必然有偶数个节点 除了空树起始节点必然不可能是空节点if(n%20||s[0].equals(#))return false;int countNum0;int countChar0;for(int i0;in;i){String s1s[i];if(!s1.equals(#)){countNum;}else{countChar;}//若前面已经是一个完整的树后序还有节点则必然不是一个有效的树的前序序列化if(in-1countCharcountNum1)return false;}//树的非空节点数必然比空节点少一个if(countChar!countNum1)return false;return true;
}方法二 栈 参考官方题解 时间复杂度O(n) 空间复杂度O(1) public boolean isValidSerialization(String preorder) {int n preorder.length();int i 0;DequeInteger stack new LinkedListInteger();stack.push(1);while (i n) {if (stack.isEmpty()) {return false;}if (preorder.charAt(i) ,) {i;} else if (preorder.charAt(i) #){int top stack.pop() - 1;if (top 0) {stack.push(top);}i;} else {// 读一个数字while (i n preorder.charAt(i) ! ,) {i;}int top stack.pop() - 1;if (top 0) {stack.push(top);}stack.push(2);}}return stack.isEmpty();
}有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
