山东网站优化公司,wordpress返回顶部代码,跨境电商开店大概流程,四川城乡建设厅官网序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时#xff0c;我们可以记录下这个节点的值。如果它是一个空节点#xff0c;我们可以使用一个标记值记录#xff0c;例如 #。_9_/ \3 2/ \ / \4 1 # 6
/ \ / \ / \
# # # # # #
例如#xff0…序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时我们可以记录下这个节点的值。如果它是一个空节点我们可以使用一个标记值记录例如 #。_9_/ \3 2/ \ / \4 1 # 6
/ \ / \ / \
# # # # # #
例如上面的二叉树可以被序列化为字符串 9,3,4,#,#,1,#,#,2,#,6,#,#其中 # 代表一个空节点。给定一串以逗号分隔的序列验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 # 。你可以认为输入格式总是有效的例如它永远不会包含两个连续的逗号比如 1,,3 。示例 1:输入: 9,3,4,#,#,1,#,#,2,#,6,#,#
输出: true
示例 2:输入: 1,#
输出: false
解题思路
因为这题连空节点都连出来了所以只需要统计空节点和正常节点是否能满足前序遍历的要求。一个正常节点必须连接两个子节点包括#节点而空节点不能拥有子节点因此存在关系 父节点除#以外后面必须有两个元素包括正常节点和#节点#节点后面不能接子节点
代码
class Solution {public boolean isValidSerialization(String preorder) {String[] split preorder.split(,);int i0,nsplit.length,slot1;while (in){if(slot0) return false;//后面还有节点没遍历完坑位已经被占慢了if(split[i].equals(#))slot--;//空节点坑位被占掉一个由于没有子节点不需要添加坑位else slot;
//坑位被占掉一个但是因为有两个子节点需要多加两个坑位所以实际上只加了一个}return slot0;}
}
