Verify Preorder Serialization of a Binary Tree

题目描述

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

解题方法

  1. stack

比如一个"3 9 # # 20 15 # # 7 # #"的preorder的serialization, 因为这里 叶子节点的none children也要用# #表示出来，preorder的左子树在右子树之前。 我们可以通过这些特性思考来找到解题方法。

verify preorder sequence那个是通过value大小来判断，而这里我们多了 #，要根据这一特点来加操作。我们发现可以通过不断去掉叶子节点 来判断，一颗合法的二叉树去掉某个叶子节点后仍应该是合法的 二叉树，所以我们根据 num, #, #这个规律来去掉叶子节点，看最后 剩下的是否只有#。

  1. 入度和出度的差

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 by 2, because it provides two out degrees. If a serialization is correct, diff should never be negative and diff will be zero when finished.

Solution

stack解法

class Solution(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        if not preorder:
            return False

        stack = []
        for x in preorder.split(","):
            stack.append(x)
            while len(stack) >= 3 and stack[-2:] == ["#", "#"] and stack[-3] != "#":
                stack.pop()
                stack.pop()
                stack.pop()
                stack.append("#")

        return stack == ["#"]

 def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        if not preorder:
            return False

        diff = 1 # for root
        for x in preorder.split(","):
            diff -= 1 # indegree - 1
            if diff < 0: # should never be below 0
                return False
            if x != "#":
                diff += 2 # if not None, outdegree + 2
        return diff == 0

Reference