331. Verify Preorder Serialization of a Binary Tree #

题目 #

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

题目大意 #

给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

解题思路 #

这道题有些人用栈，有些用栈的深度求解。换个视角。如果叶子结点是 null，那么所有非 null 的结点(除了 root 结点)必然有 2 个出度，1 个入度(2 个孩子和 1 个父亲，孩子可能为空，但是这一题用 “#” 代替了，所以肯定有 2 个孩子)；所有的 null 结点只有 0 个出度，1 个入度(0 个孩子和 1 个父亲)。

我们开始构建这颗树，在构建过程中，我们记录出度和度之间的差异 diff = outdegree - indegree。当下一个节点到来时，我们将 diff 减 1，因为这个节点提供了一个度。如果这个节点不为 null，我们将 diff 增加 2，因为它提供两个出度。如果序列化是正确的，则 diff 应该永远不会为负，并且 diff 在完成时将为零。最后判断一下 diff 是不是为 0 即可判断它是否是正确的二叉树的前序序列化。

代码 #

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
}