- 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 | tmp |

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 | Example 1: |

1 | Example 2: |

1 | Example 3: |

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 | class Solution { |

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,

- if nullCnt > nodeCnt+1, the tree is invalid.
- if nullCnt < nodeCnt+1, the tree is incomplete.
- 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 | class Solution { |

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 | def isValidSerialization(self, preorder): |

Java

1 | public boolean isValidSerialization(String preorder) { |

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 | class Solution(object): |

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 | class Solution(object): |