331. Verify Preorder Serialization of a Binary Tree

  • 35.6%

https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/#/description

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
2
3
4
5
6
7
8
tmp
_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”.

1
2
3
Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true
1
2
3
Example 2:
"1,#"
Return false
1
2
3
Example 3:
"9,#,#,1"
Return false

https://discuss.leetcode.com/topic/45326/c-4ms-solution-o-1-space-o-n-time

C++ 4ms solution, O(1) space, O(n) time

The capacity is the number of node that can be put in the tree. The initial value is 1, which means there can be a root.

When adding a node, capacity–;

When adding a non-NULL node, it means we obtains two more leafs, then capacity +=2.

The final capacity should be equal to 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
bool isValidSerialization(string preorder) {
if (preorder.empty()) return false;
preorder+=',';
int sz=preorder.size(),idx=0;
int capacity=1;
for (idx=0;idx<sz;idx++){
if (preorder[idx]!=',') continue;
capacity--;
if (capacity<0) return false;
if (preorder[idx-1]!='#') capacity+=2;
}
return capacity==0;
}
};

https://discuss.leetcode.com/topic/36100/straight-forward-c-solution-with-explanation

Straight-forward C++ solution with explanation

The idea is simple.

Denote the number of null nodes as nullCnt, the number of actual nodes as nodeCnt.

For a binary tree, the number of null nodes is always the number of actual nodes plus 1. nullCnt==nodeCnt+1;

So,

  1. if nullCnt > nodeCnt+1, the tree is invalid.
  2. if nullCnt < nodeCnt+1, the tree is incomplete.
  3. if nullCnt==nodeCnt+1, the tree is complete and can’t be extended.

We just need to keep track of nullCnt and nodeCnt as we go through the sequence and check these conditions above.

Actually, recording nullCnt-nodeCnt is enough, so you can further improve the code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
bool isValidSerialization(string preorder) {
int nodeCnt=0,nullCnt=0;
vector<string> v=splitStr(preorder,',');
for(int i = 0; i<v.size(); i++){
if(v[i]=="#") ++nullCnt;
else ++nodeCnt;
if(nullCnt>=nodeCnt+1 && i!=v.size()-1) return false;
}
return nullCnt==nodeCnt+1;
}

vector<string> splitStr(string str, char delimiter){
vector<string> r;
string tmpstr;
while (!str.empty()){
int ind = str.find_first_of(delimiter);
if (ind == -1){
r.push_back(str);
str.clear();
}
else{
r.push_back(str.substr(0, ind));
str = str.substr(ind + 1, str.size() - ind - 1);
}
}
return r;
}
};

Edit:

The algorithm scans the string one node at a time from the beginning, once it finds nullCnt>nodeCnt+1, it stops and return false.

If it finds nullCnt==nodeCnt+1, that means by now, the tree is valid(otherwise the algorithm would return false before this) and complete, if there are more nodes to come, it returns false; if it’s the last node, the algorithm returns true.

If it finds nullCnt< nodeCnt+1, that means the tree is incomplete but not invalid(or the algorithm would return false before this) by now, if this is the last node and no more nodes comes after it, the tree is invalid.

Example:

“#,1,#” 1st node is #, nullCnt==1, nodeCnt==0, nullCnt==nodeCnt+1, the tree is complete by now, but there are more nodes after it, so it’s invalid.

“1, #” 1st node is 1, nullCnt==0, nodeCnt==1, nullCnt< nodeCnt+1, the tree is incomplete, but there are more nodes after it, so we proceed, 2nd node is #, nullCnt==1, nodeCnt==1, nullCnt< nodeCnt+1, the tree is incomplete and there are no more nodes left, so it’s invalid.

Edit2:

Why for a binary tree, nullCnt==nodeCnt+1?

For an empty binary tree, nullCnt=1, nodeCnt=0, nullCnt==nodeCnt+1.

Each time we add an actual node, we take the place of one null node and create two null nodes, so the net gain of null node is one, which is also the net gain of actual node. Thus, the actual nodes and null nodes will increase by the same amount, which means nullCnt==nodeCnt+1 will always hold.


https://discuss.leetcode.com/topic/36034/6-lines-python-7-lines-java

Python

1
2
3
4
5
6
7
def isValidSerialization(self, preorder):
need = 1
for val in preorder.split(','):
if not need:
return False
need -= ' #'.find(val)
return not need

Java

1
2
3
4
5
6
7
8
9
public boolean isValidSerialization(String preorder) {
int need = 1;
for (String val : preorder.split(",")) {
if (need == 0)
return false;
need -= " #".indexOf(val);
}
return need == 0;
}

52ms, 76.41%, 150/150, April.26th, 2016

https://leetcode.com/discuss/84257/simplest-python-solution-with-explanation-stack-recursion

The simplest python solution with explanation (no stack, no recursion)

We just need to remember how many empty slots we have during the process.

Initially we have one ( for the root ).

for each node we check if we still have empty slots to put it in.

  • a null node occupies one slot.
  • a non-null node occupies one slot before he creates two more. the net gain is one.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution(object):
def isValidSerialization(self, preorder):
"""
:type preorder: str
:rtype: bool
"""
# remember how many empty slots we have
# non-null nodes occupy one slot but create two new slots
# null nodes occupy one slot

p = preorder.split(',')

#initially we have one empty slot to put the root in it
slot = 1
for node in p:

# no empty slot to put the current node
if slot == 0:
return False

# a null node?
if node == '#':
# ocuppy slot
slot -= 1
else:
# create new slot
slot += 1

#we don't allow empty slots at the end
return slot==0

https://discuss.leetcode.com/topic/35977/simple-python-solution-using-stack-with-explanation

Simple Python solution using stack. With Explanation.

This is very simple problem if you use stacks. The key here is, when you see two consecutive “#” characters on stack, pop both of them and replace the topmost element on the stack with “#”. For example,

preorder = 1,2,3,#,#,#,#

Pass 1: stack = [1]

Pass 2: stack = [1,2]

Pass 3: stack = [1,2,3]

Pass 4: stack = [1,2,3,#]

Pass 5: stack = [1,2,3,#,#] -> two #s on top so pop them and replace top with #. -> stack = [1,2,#]

Pass 6: stack = [1,2,#,#] -> two #s on top so pop them and replace top with #. -> stack = [1,#]

Pass 7: stack = [1,#,#] -> two #s on top so pop them and replace top with #. -> stack = [#]

If there is only one # on stack at the end of the string then return True else return False.

Here is the code for that,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution(object):
def isValidSerialization(self, preorder):
"""
:type preorder: str
:rtype: bool
"""
stack = []
top = -1
preorder = preorder.split(',')
for s in preorder:
stack.append(s)
top += 1
while(self.endsWithTwoHashes(stack,top)):
h = stack.pop()
top -= 1
h = stack.pop()
top -= 1
if top < 0:
return False
h = stack.pop()
stack.append('#')
#print stack
if len(stack) == 1:
if stack[0] == '#':
return True
return False

def endsWithTwoHashes(self,stack,top):
if top<1:
return False
if stack[top]=='#' and stack[top-1]=='#':
return True
return False
谢谢你,可爱的朋友。