2024.3.31力扣每日一题——验证二叉树的前序序列化

本文主要是介绍2024.3.31力扣每日一题——验证二叉树的前序序列化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2024.3.31

- - 题目来源
  - 我的题解
  - - 方法一计数
    - 方法二栈

题目来源

力扣每日一题；题序：331

我的题解

方法一计数

当只有一个节点并且是空节点，则表示是空树，是一个正确的序列化
正确的序列化节点数必然是偶数个，若不是偶数个，则不是一个正确的序列化
除了空树起始节点必然不可能是空节点
一个正确的序列化，必然非空节点数量比空节点数量少1

时间复杂度：O(n)
空间复杂度：O(1)

public boolean isValidSerialization(String preorder) {//空树if(preorder.equals("#"))return true;String[] s=preorder.split(",");int n=s.length;//包含空节点的树必然有偶数个节点   除了空树起始节点必然不可能是空节点if(n%2==0||s[0].equals("#"))return false;int countNum=0;int countChar=0;for(int i=0;i<n;i++){String s1=s[i];if(!s1.equals("#")){countNum++;}else{countChar++;}//若前面已经是一个完整的树，后序还有节点，则必然不是一个有效的树的前序序列化if(i<n-1&&countChar==countNum+1)return false;}//树的非空节点数必然比空节点少一个if(countChar!=countNum+1)return false;return true;
}

方法二栈

参考官方题解

时间复杂度：O(n)
空间复杂度：O(1)

public boolean isValidSerialization(String preorder) {int n = preorder.length();int i = 0;Deque<Integer> stack = new LinkedList<Integer>();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();
}