LeetCode刷题实战331:验证二叉树的前序序列化
程序IT圈
共 4388字,需浏览 9分钟
·
2021-07-27 01:03
示例
示例 1:
输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true
示例 2:
输入: "1,#"
输出: false
示例 3:
输入: "9,#,#,1"
输出: false
解题
class Solution {
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();
}
}
作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/solution/yan-zheng-er-cha-shu-de-qian-xu-xu-lie-h-jghn/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
LeetCode刷题实战325:和等于 k 的最长子数组长度
评论