每日一题 2019 - 01 - 23
题目:
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 #
.
1 | _9_ |
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:
1 | Input: "9,3,4,#,#,1,#,#,2,#,6,#,#" |
Example 2:
1 | Input: "1,#" |
Example 3:
1 | Input: "9,#,#,1" |
解法:
这个题让我们判断给定的序列是不是二叉树的先序遍历序列,这里我们需要注意给定的序列的特点:
- 任意一个非空结点一定有两个子结点,这两个子结点可以为空,也即
#
- 一颗空树的序列为
#
,满足题意要求
同时我们还需要注意题中所给的二叉树的一个特点就是:
- 空结点的个数 = 非空结点的个数 + 1
所以如果我们在遍历序列的过程中发现#
的个数大于当前已经遍历过的非空节点的个数 + 1,那么证明这颗树是不存在的,有了这个思路我们就可以完成这个题的解答。
代码:
1 | class Solution { |