leetcode Verify Preorder Serialization of a Binary Tree

leetcode 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 #.
1
2
3
4
5
6
7
8
     _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: "9,3,4,#,#,1,#,#,2,#,6,#,#" Return true

Example 2: "1,#" Return false

Example 3: "9,#,#,1" Return false 题目地址：leetcode Verify Preorder Serialization of a Binary Tree

题意：给定二叉树的前序遍历，要你在不构造树的情况下，判断树是否合法。

其实是一道google电面的题，之前在一亩三分地看过。

思路：

栈
入度和出度的差

栈

这个方法简单的说就是不断的砍掉叶子节点。最后看看能不能全部砍掉。

已例子一为例，："9,3,4,#,#,1,#,#,2,#,6,#,#" 遇到x # #的时候，就把它变为 #

我模拟一遍过程：

9,3,4,#,# => 9,3,# 继续读
9,3,#,1,#,# => 9,3,#,# => 9,# 继续读
9,#2,#,6,#,# => 9,#,2,#,# => 9,#,# => #

合法的情况最后一定是一个#，python代码如下:

Python

class Solution(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        stack = []
        for x in preorder.split(','):
            stack += [x]
            while len(stack) >= 3 and stack[-2:] == ['#','#'] and stack[-3]!='#':
                stack = stack[:-3] +['#'] # pop *3 and append #
        return len(stack) == 1 and stack[0] == '#'

入度和出度的差

看了 dietpepsi 的代码，确实思路比我上面的更胜一筹：

In a binary tree, if we consider null as leaves, then

all non-null node provides 2 outdegree and 1 indegree (2 children and 1 parent), except root

all null node provides 0 outdegree and 1 indegree (0 child and 1 parent).

Suppose we try to build this tree. During building, we record the difference between out degree and in degree diff = outdegree - indegree. When the next node comes, we then decrease diff by 1, because the node provides an in degree. If the node is not null, we increase diff by2, because it provides two out degrees. If a serialization is correct, diff should never be negative and diff will be zero when finished.

from :https://leetcode.com/discuss/83824/7-lines-easy-java-solution

我这里翻译一下：

对于二叉树，我们把空的地方也作为叶子节点（如题目中的#），那么有

所有的非空节点提供2个出度和1个入度（根除外）
所有的空节点但提供0个出度和1个入度

我们在遍历的时候，计算diff = outdegree - indegree. 当一个节点出现的时候，diff - 1，因为它提供一个入度；当节点不是#的时候，diff+2(提供两个出度) 如果序列式合法的，那么遍历过程中diff >=0 且最后结果为0.

Java

public boolean isValidSerialization(String preorder) {
    String[] nodes = preorder.split(",");
    int diff = 1;
    for (String node: nodes) {
        if (--diff < 0) return false;
        if (!node.equals("#")) diff += 2;
    }
    return diff == 0;
}

本文是leetcode 331 Verify Preorder Serialization of a Binary Tree 的题解，