Akik Look at that coder

Public account: Look at that code farmer

331. Verify the sequential serialization of the binary tree

Title description:

Given a comma-separated sequence, verify that it is the correct preserialization of the binary tree.

Write a feasible algorithm without reconstructing the tree.

One way to serialize a binary tree is to use a pre-order traversal.

When we encounter a non-empty node, we can record the value of the node.

If it is an empty node, we can record it with a token value, such as #.

One way to serialize a binary tree is to use a pre-order traversal. When we encounter a non-empty node, we can record the value of the node. If it is an empty node, we can record it with a token value, such as #.Copy the code

For example, the binary tree above could be serialized as a string"9 and 4, #, # 1, #, #, 2 #, 6, #, #"Where # represents an empty node. Each comma-separated character is either an integer or a representationnullPointer to theThe '#'. You can assume that the input format is always valid, such that it will never contain two consecutive commas, such as"1, 3," 
Copy the code

Input:"9 and 4, #, # 1, #, #, 2 #, 6, #, #"Output:trueInput:"# 1,"Output:falseInput:"9, #, #, 1"Output:false
Copy the code

The code analysis

We can solve this problem with both input and output

The sum of the inputs of all nodes is equal to the sum of the outputs

You can use this feature to determine whether the input sequence is valid

Let’s use an example to illustrate what this means, as shown in the figure below, which is a binary tree

node1For out of degrees2For, in degrees0node2.5For out of degrees2For, in degrees1node3.4.6.7For out of degrees2For, in degrees1The output degree of the empty node # is0For, in degrees1The output degrees of all nodes sum to14The sum of all nodes is14
Copy the code

That is, the sum of the inputs of all nodes in a binary tree is equal to the sum of the outputs

We just iterate through the string once and calculate the difference between the outgoing and incoming degrees of each node diff, i.e., diff= outgoing - incoming degrees. When traversing through any node, diff>= is required0, the reason is that the child nodes of this node have not been traversed, so the out degree should be greater than or equal to the in degree. If the diff"0, represents out degree < in degree. The binary tree is invalid and returnsfalse
Copy the code

Therefore, the problem solving code is

class Solution(object) :def isValidSerialization(self.preorder) :nodes = preorder.split(', ')
        diff = 1
        for node in nodes:
            diff -= 1
            if diff < 0:
                return False
            ifnode ! =The '#':
                diff += 2
        return diff == 0
Copy the code

Here’s why diff is initialized to 1 in the following code.

Because when we add a non-empty node, we subtract an in degree and add two out degrees. But since the root node has no parent, its degree of entry is 0 and its degree of exit is 2. So the diff is initialized to 1 so that when you add the root node, you subtract an in and add two outs, and the diff should be exactly 2.

If you find this helpful:

1. Click “like” to support it, so that more people can see this article

2, pay attention to the public number: look at that code farmers, we study together and progress together.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign