leetcode331-验证二叉树的前序序列化

原题

序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时,我们可以记录下这个节点的值。如果它是一个空节点,我们可以使用一个标记值记录,例如 #

     _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

示例 3:

输入: "9,#,#,1"
输出: false

解法

思想

可能导致前序序列化验证失败的情况有:

  1. null做空节点
  2. 子节点不完全
  #       1
 / \     / \
1   2   3

假设任一状态待填充的节点数为count,第一种情况会导致在某一个时刻count小于0,第二种情况会导致最后count大于0。而这两种情况是不会同时存在的。

每次遇到一个节点count的值减一,遇到一个非null的节点count的值加二,最后看count是否为0。

代码

class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] nodes = preorder.split(",");
        int count = 1;
        for(String i:nodes){
            count-=1;
            if(count<0) return false;
            if(!i.equals("#")) count+=2;
        }
        return count==0;
    } 
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode331-%e9%aa%8c%e8%af%81%e4%ba%8c%e5%8f%89%e6%a0%91%e7%9a%84%e5%89%8d%e5%ba%8f%e5%ba%8f%e5%88%97%e5%8c%96/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月26日
下一篇 2020年1月27日

相关推荐

  • leetcode287-寻找重复数

    原题 给定一个包含 n + 1 个整数的数组 nums ,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。 …

    2020年1月7日
    080
  • leetcode219-存在重复元素II

    原题 给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的绝对值最大为 k。 示例1…

    算法 2019年12月24日
    0160
  • leetcode111-二叉树的最小深度

    原题 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,nul…

    算法 2020年3月25日
    0210
  • 海量数据去重-由BitMap引出的布隆过滤器

    本文参考资源: 那些惊艳的算法们(一)——布隆过滤器_C/C++_xinzhongtianxia的博客-CSDN博客 详解布隆过滤器的原理、使用场景和注意事项 - 简书 概述 昨天…

    2020年2月28日
    01.3K0
  • 剑指offer46-把数字翻译成字符串

    原题 给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编…

    算法 2020年2月29日
    0110
  • leetcode225--用队列实现栈

    原题 使用队列实现栈的下列操作: push(x) – 元素 x 入栈 pop() – 移除栈顶元素 top() – 获取栈顶元素 empty() – 返回栈是否为空 注意: 你只能…

    算法 2019年12月13日
    0100
  • leetcode443-压缩字符串

    原题 给定一组字符,使用原地算法将其压缩。 压缩后的长度必须始终小于或等于原数组长度。 数组的每个元素应该是长度为1 的字符(不是 int 整数类型)。 在完成原地修改输入数组后,…

    算法 2020年5月28日
    060
  • leetcode744-寻找比目标字母大的最小字母

    原题 给定一个只包含小写字母的有序数组letters 和一个目标字母 target,寻找有序数组里面比目标字母大的最小字母。 数组里字母的顺序是循环的。举个例子,如果目标字母tar…

    算法 2020年1月5日
    0130
  • leetcode153-寻找旋转排序数组中的最小值

    原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值,…

    算法 2020年1月3日
    080
  • leetcode99-恢复二叉搜索树

    原题 二叉搜索树中的两个节点被错误地交换。 请在不改变其结构的情况下,恢复这棵树。 示例 1: 输入: [1,3,null,null,2]    1 …

    算法 2020年3月1日
    070

发表回复

登录后才能评论