leetcode:331. 验证二叉树的前序序列化【栈顶消消乐 or 入度出度】

栈模拟分析

如果最后碰到’digit # #‘的情况可以把其代换成一个’#’
然后最后判断剩下的是否是一个’#'即可

这种就是经典的栈顶消消乐

栈ac code

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        # 栈模拟
        # 'digit # #'合并成 # 即可
        pre_lst = preorder.split(',')
        st = []

        for item in pre_lst:
            st.append(item)
            while len(st) >= 3 and st[-1] == '#' and st[-2] == '#' and st[-3] != '#':
                st.pop(), st.pop(), st.pop()
                st.append('#')
        
        #print(st)
        return len(st) == 1 and st[0] == '#'

出度入度分析

跟的入度0出度2
非叶子入度1出度2
叶子入度1出度0

按照先序遍历 初始diff = 1
先diff减一 若其小于0就False了
因为最后要支撑diff == 0
然后如果是非叶子，diff += 2（出度加2）

就是遍历过程中不可能出现总入度 > 总出度的情况
有点难理解

出度入度ac code

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        diff = 1
        pre_lst = preorder.split(',')

        for item in pre_lst:
            diff -= 1
            if diff < 0:
                return False
            if item != '#':
                diff += 2
        
        return diff == 0

总结

这道题应该栈模拟更容易理解和上手
通过栈顶消消乐来完成合法前序的判断即可

最后

以上就是淡然萝莉为你收集整理的leetcode:331. 验证二叉树的前序序列化【栈顶消消乐 or 入度出度】的全部内容，希望文章能够帮你解决leetcode:331. 验证二叉树的前序序列化【栈顶消消乐 or 入度出度】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。