网站建设类公司新闻,徐州市城乡建设局门户网站,网站建设互联网营销营销推广,网站按抓取手机软件贵阳验证二叉树的前序序列化
题目要求 解题思路
方法一#xff1a;栈 栈的思路是「自底向上」的想法。下面要结合本题是「前序遍历」这个重要特点。
我们知道「前序遍历」是按照「根节点-左子树-右子树」的顺序遍历的#xff0c;只有当根节点的所有左子树遍历完成之后#xf…验证二叉树的前序序列化
题目要求 解题思路
方法一栈 栈的思路是「自底向上」的想法。下面要结合本题是「前序遍历」这个重要特点。
我们知道「前序遍历」是按照「根节点-左子树-右子树」的顺序遍历的只有当根节点的所有左子树遍历完成之后才会遍历右子树。对于本题的输入我们可以先判断「左子树」是否有效的然后再判断「右子树」是否有效的最后判断「根节点-左子树-右子树」是否为有效的。这个思路类似于递归而把递归改写成循环时就会使用「栈」这就是本题使用「栈」的原因。
下面的重点是如何判断一棵子树是否有效首先考虑最简单情况怎么判断一个节点是叶子节点很明显当一个节点的两个孩子都是 #空的时候该节点就是叶子节点。 当一个节点不是叶子节点的时候那么它必定至少有一个孩子非空有两种情况
两个孩子都非#空 一个孩子为#空另一个孩子非#空 为了兼容这两个情况我们想出了本题的一个重磅级的技巧把有效的叶子节点使用 # 代替。 比如把 4## 替换成 # 。此时叶子节点会变成空节点 具体操作流程示例如下
如输入9,3,4,#,#,1,#,#,2,#,6,#,#当遇到 x,#,# 的时候就把它变为 #。
模拟一遍过程
[9,3,4,#,#] [9,3,#]继续[9,3,#,1,#,#] [9,3,#,#] [9,#] 继续[9,#2,#,6,#,#] [9,#,2,#,#] [9,#,#] [#]结束
方法二计算入度出度
背景知识
入度有多少个节点指向它出度它指向多少个节点。
我们知道在树甚至图中所有节点的入度之和等于出度之和。可以根据这个特点判断输入序列是否为有效的
在一棵二叉树中
每个空节点 #会提供 0 个出度和 1 个入度。每个非空节点会提供 2 个出度和 1 个入度根节点的入度是 0。
我们只要把字符串遍历一次每个节点都累加 diff 出度 - 入度 。在遍历到任何一个节点的时候要求diff 0原因是还没遍历到该节点的子节点所以此时的出度应该大于等于入度。当所有节点遍历完成之后整棵树的 diff 0。
这里解释一下为什么下面的代码中 diff 的初始化为 1。因为我们加入一个非空节点时都会对 diff 先减去 1入度再加上 2出度。但是由于根节点没有父节点所以其入度为 0出度为 2。因此 diff 初始化为 1是为了在加入根节点的时候diff 先减去 1入度再加上 2出度此时 diff 正好应该是2.
代码
方法一 class Solution(object): def isValidSerialization(self, preorder): stack [] for node in preorder.split(,): stack.append(node) while len(stack) 3 and stack[-1] stack[-2] # and stack[-3] ! #: stack.pop(), stack.pop(), stack.pop() stack.append(#) return len(stack) 1 and stack.pop() # 方法二 class Solution(object): def isValidSerialization(self, preorder): nodes preorder.split(,) diff 1 for node in nodes: diff - 1 if diff 0: return Falseif node ! #: diff 2 return diff 0 复杂度分析
方法一
时间复杂度 O ( N ) O(N) O(N)空间复杂度 O ( N ) O(N) O(N)
方法二
时间复杂度 O ( N ) O(N) O(N)空间复杂度 O ( 1 ) O(1) O(1)
参考
负雪明烛
