331. Verify Preorder Serialization of a Binary Tree #

Problem #

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

Problem Summary #

Given a comma-separated sequence, verify whether it is a correct preorder serialization of a binary tree. Write a feasible algorithm without reconstructing the tree.

Solution Ideas #

Some people use a stack for this problem, while others solve it using the depth of a stack. Let’s look at it from another perspective. If leaf nodes are null, then every non-null node (except the root node) must have 2 outdegrees and 1 indegree (2 children and 1 parent; children may be null, but in this problem they are represented by “#”, so there must be 2 children); every null node has only 0 outdegrees and 1 indegree (0 children and 1 parent).

We start constructing this tree, and during the construction process, we record the difference between outdegree and indegree: diff = outdegree - indegree. When the next node arrives, we decrement diff by 1, because this node consumes one indegree. If this node is not null, we increment diff by 2, because it provides two outdegrees. If the serialization is correct, diff should never be negative, and diff will be zero when finished. Finally, simply check whether diff is 0 to determine whether it is a correct preorder serialization of a binary tree.

Code #

package leetcode

import "strings"

func isValidSerialization(preorder string) bool {
	nodes, diff := strings.Split(preorder, ","), 1
	for _, node := range nodes {
		diff--
		if diff < 0 {
			return false
		}
		if node != "#" {
			diff += 2
		}
	}
	return diff == 0
}