331 Verify Preorder Serialization of a Binary Tree

1. Question

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_
2
/ \
3
3 2
4
/ \ / \
5
4 1 # 6
6
/ \ / \ / \
7
# # # # # #
Copied!
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'#'representingnullpointer.
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:"9,3,4,#,#,1,#,#,2,#,6,#,#" Returntrue
Example 2:"1,#" Returnfalse
Example 3:"9,#,#,1" Returnfalse

2. Implementation

(1) Stack
思路: 这里用stack和利用stack做preorder traversal类似,可以分以下几种情况考虑:
  1. 1.
    如果当前的node是数字,说明我们将以这个node作为根展开,将node push到stack
  2. 2.
    如果当前的node是#,
2.1. 而栈顶是数字,说明当前的node代表的是left null child,我们将它放在stack上作为一个记号,这样接下来node就知道它自己是right child
2.2. 而栈顶是#,说明当前node是right null child, 这时我们至少call两次 stack.pop(),代表以node的parent作为根的subtree cancel,同时我们查看栈顶的是数字还是#
2.2.1. 如果栈顶是数字,说明我们刚刚将一个node t从栈顶弹出,而这个node t是一个left child, 这时我们需要将#留在stack里,作为记号,让后面的node知道它自己是right child
2.2.2 如果栈顶是#, 说明我们刚刚取消了一个以node t为根的subtree, 而node t是一个right child,所以我们继续将stack元素弹出
1
class Solution {
2
public boolean isValidSerialization(String preorder) {
3
if (preorder == null || preorder.length() == 0) {
4
return false;
5
}
6
7
String[] nodes = preorder.split(",");
8
9
Stack<String> stack = new Stack<>();
10
11
for (String node : nodes) {
12
while (node.equals("#") && !stack.isEmpty() && stack.peek().equals("#")) {
13
stack.pop();
14
15
if (stack.isEmpty()) {
16
return false;
17
}
18
19
stack.pop();
20
}
21
stack.push(node);
22
}
23
return stack.size() == 1 && stack.peek().equals("#");
24
}
25
}
Copied!
(2) Graph Property
思路: 这种解法利用了树的入度和出度是相同的性质。我们定义diff = Outdegree - Indegree, 对于每个node,其入度为1,所以diff也相应减1。而如果node不是#的话,出度为2,所以diff也相应加2。需要注意的是,我们将diff初始化为1,原因是我们将root也作为一个普通的node处理,然而root的入度是0, 出度是2,所以我们将diff初始化为1,这样root作为普通node,它的diff也是1
1
class Solution {
2
public boolean isValidSerialization(String preorder) {
3
if (preorder == null || preorder.length() == 0) {
4
return false;
5
}
6
7
String[] nodes = preorder.split(",");
8
9
int diff = 1;
10
for (String node : nodes) {
11
--diff;
12
if (diff < 0) {
13
return false;
14
}
15
if (!node.equals("#")) {
16
diff += 2;
17
}
18
}
19
return diff == 0;
20
}
21
}
Copied!

3. Time & Space Complexity

Stack: 时间复杂度O(n), 空间复杂度O(n)
Graph Property : 时间复杂度O(n), 空间复杂度O(1)