​LeetCode刷题实战331:验证二叉树的前序序列化

程序IT圈

共 4388字,需浏览 9分钟

 ·

2021-07-27 01:03

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-320题汇总,希望对你有点帮助!

LeetCode刷题实战321:拼接最大数

LeetCode刷题实战322:零钱兑换

LeetCode刷题实战323:无向图中连通分量的数目

LeetCode刷题实战324:摆动排序 II

LeetCode刷题实战325:和等于 k 的最长子数组长度

LeetCode刷题实战326:3的幂
LeetCode刷题实战327:区间和的个数
LeetCode刷题实战328:奇偶链表
LeetCode刷题实战329:矩阵中的最长递增路径
LeetCode刷题实战330:按要求补齐数组

浏览 18
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报