leetcode331. Verify Preorder Serialization of a Binary Tree

题目要求

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character '#' representing null pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".

Example 1:

Input: "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true
Example 2:

Input: "1,#"
Output: false
Example 3:

Input: "9,#,#,1"
Output: false

思路和代码

我们知道,任何两个节点都可以和位于左边的非叶节点构成一棵有三个节点的树。如果我们从右往左看先序遍历,就知道后两个节点如果遇到第三个节点,则该节点就应当是这两个节点的父节点。我们可以将每一个#看做一个根节点,每遇到#就将记录的根节点数加一,当遇到数字时,则代表该数字应当能够和两个节点构成新的树,并且该数字成为新的根节点,因此需要将根节点数量减一。如果在遍历的过程中根节点数量小于1,则说明这棵树有问题。而如果遍历结束之后,剩下的根节点数不等于1,也说明这个先序遍历存在问题。

    public boolean isValidSerialization(String preorder) {
        if(preorder==null) return false;
        if(preorder.length() == 0) return true;
        String[] nodes = preorder.split(",");
        int nodeCount = 0;
        for(int i = nodes.length - 1; i >= 0 ; i--) {
            if(nodes[i].equals("#")) {
                nodeCount++;
            } else {
                nodeCount--;
            }
            if(nodeCount <= 0) return false;
        }
        return nodeCount == 1;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏米扑专栏

VC Tab Control 切换窗体

1. 新建一个MFC工程,取名xyTabControl,选择Dialog based,然后Finish。

30560
来自专栏米扑专栏

VC 读写注册表

近来由于需要在自己写的程序中对注册表进行操作。总结些经验,并做个一个DEMO供日后使用,现在把它拿出来和大家分享…

32420
来自专栏米扑专栏

String、StringBuilder、StringBuffer 用法比较

String、StringBuilder、StringBuffer 三个类源自JDK的 java/lang/ 目录下:

18740
来自专栏米扑专栏

VC Picture Control 图片点击事件

VC 中Picture Control 添加图片和点击事件,比C#等语言稍微较麻烦

21780
来自专栏米扑专栏

ArrayList、LinkedList、 Vector、Map 用法比较

ArrayList和Vector是采用数组方式存储数据,此数组元素总数大于实际存储的数据个数以便增加和插入元素,二者都允许直接序号索引元素,但是插入数据要移动数...

17230
来自专栏米扑专栏

VC Picture Control显示BMP图片

28140
来自专栏米扑专栏

CString 和 char* 类型转化

CString 是一种很有用的数据类型。它们很大程度上简化了MFC中的许多操作,使得MFC在做字符串操作的时候方便了很多。不管怎样,使用CString有很多特殊...

1.7K20
来自专栏米扑专栏

数组中数对差最大

数组{2, 4, 1, 16, 7, 5, 11, 9}中,数对之差的最大值是11(16 - 5)

24520
来自专栏米扑专栏

VC char和TCHAR之间转换

char:计算机编程语言(c、c++、java、VFP等)中可容纳单个字符的一种基本数据类型。

17430
来自专栏米扑专栏

数组中最大和的子数组

输入一个整型数组,数据元素有正数也有负数,求元素组合成连续子数组之和最大的子数组,要求时间复杂度为O(n)。

14030

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励