算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 验证二叉树的前序序列化,我们先来看题面:
https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/
示例 1:
输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true
示例 2:
输入: "1,#"
输出: false
示例 3:
输入: "9,#,#,1"
输出: false
方法一:栈
我们可以定义一个概念,叫做槽位。一个槽位可以被看作「当前二叉树中正在等待被节点填充」的那些位置。
二叉树的建立也伴随着槽位数量的变化。每当遇到一个节点时:
如果遇到了空节点,则要消耗一个槽位;
如果遇到了非空节点,则除了消耗一个槽位外,还要再补充两个槽位。
此外,还需要将根节点作为特殊情况处理。
我们使用栈来维护槽位的变化。栈中的每个元素,代表了对应节点处剩余槽位的数量,而栈顶元素就对应着下一步可用的槽位数量。当遇到空节点时,仅将栈顶元素减 1;当遇到非空节点时,将栈顶元素减 1 后,再向栈中压入一个 2。无论何时,如果栈顶元素变为 0,就立刻将栈顶弹出。
遍历结束后,若栈为空,说明没有待填充的槽位,因此是一个合法序列;否则若栈不为空,则序列不合法。此外,在遍历的过程中,若槽位数量不足,则序列不合法。
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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。