The problem

Verify Preorder Serialization of a Binary Tree Medium

One way to serialize a binary tree is to use preorder 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 '#'.

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 preorder, return true if it is a correct preorder traversal serialization of a binary tree.

It is guaranteed that 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,".

Note: You are not allowed to reconstruct the tree.

 

Example 1:

Input: preorder = "4, 9 #, # 1, #, #, 2 #, 6, #, #" Output: trueCopy the code

Example 2:

Input: preorder = "1,#"
Output: false
Copy the code

Example 3:

Input: preorder = "9,#,#,1"
Output: false
Copy the code

Constraints:

  • 1 <= preorder.length <= 10^4
  • preorder consist of integers in the range [0, 100] and The '#' separated by commas ', '.

Their thinking

Before we do that, let’s review what sequential serialization of binary trees is. The binary tree in the figure is serialized to F,B,A,D,C,E,G,I,H in the order shown by the dotted line in the figure below, which is the pre-serialization. If the subject setting, expressed with # blank nodes, is the result of the antecedent serialization F, B, A, #, #, D, C, #, #, E, #, #, #, G, I, H, #.

So how do you verify that a sequence is a legitimate pre-sequence of a binary tree? First, the parent node cannot be #. For example, 9,#,#,1 is illegal. Second, the parent node must have two children, such as 1, and # is illegal. In other words, the conditions for judging legality are:

  1. All legal parent nodes must have two children
  2. All child nodes must have a valid parent

How do you check this logic with a program? We first need to find a way to locate the location of a node’s parent node and child node, to check whether they are valid. Imagining # to the figure above, we can see that if a node is a left child, its parent is its previous element in the sequence. Conversely, if an element in the sequence is a legal parent, nums[I]! = “#”, then the element following it is its left child node.

Conversely, an element in a sequence is a right child if the preceding element is not a legal parent, i.e. Nums [i-1] == “#”. The parent of the child node on the right needs to be found in the legal parent node traversed previously. Therefore, we need to save the traversed legal parent node for the parent node search of the child node on the right.

We know that a legal parent node can only have two children, and its left child node is already determined to be the element after it, so it can only be used once in a parent node lookup. Also, in parent node lookups, we don’t care about the value of the node as long as it’s not #. So we can use a counter, parentCandidateCnt, to count the number of valid parents currently available. When traversing the sequence, parentCandidateCnt++ is encountered, and parentCandidateCnt– is encountered when the right child node is encountered.

If the final parentCandidateCnt == 0, then all legal parent nodes have found two child nodes. In this way, the condition for judging whether it is legal is satisfied. When parentCandidateCnt– is executed on the right child node, if parentCandidateCnt > 0, it indicates that the parent node is found, and condition 2 to determine whether it is legal is satisfied.

Refer to the answer


public class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] nums = preorder.split(",");
        int n = nums.length;

        int parentCandidateCnt = 0;

        for (int i = 0; i < n; i++) {
            // in preorder traversal, the left child will be right after it's parent
            // which means normally nums[i] is the left child of nums[i - 1]
            // but # can't be a parent, so when nums[i - 1] == #, nums[i] is should 
            // be a right child, and we need find its parent from candidates
            if (i > 0 && "#".equals(nums[i - 1]) {if (parentCandidateCnt > 0) {
                    parentCandidateCnt--;
                } else {
                    // if no candidate left, then return false
                    return false; }}// the nodes that is not # can be a parent node
            if (!"#".equals(nums[i])) { parentCandidateCnt++; }}// if all parent candidates have found their children return true
        return parentCandidateCnt == 0; }}Copy the code

Expand training

Let’s challenge a similar binary tree problem!

[Leetcode] [Medium] Count Good Nodes in Binary Tree Good statistics in the Binary Tree node, the number of | Java [Leetcode] [Medium] Maximum Product of Splitted Binary Tree split the biggest product | Java Binary Tree

Or check out the author’s LeetCode column for additional questions of interest!

Juejin. Cn/column / 6997…

The data link

The original leetcode.com/problems/ve…