Question

Formatted question description: https://leetcode.ca/all/331.html

 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

 @tag-tree

Algorithm

The number of digits is always one less than #
The last one must be #
leaf node: number, #, #

If we initialize a counter to 0,

When a number is encountered, the counter increases by 1,
When the # sign is encountered, the counter is decreased by 1, Then the counter should still be 0 at the end.

Two examples that return False, #,7,6,9,#,#,# and 7,2,#,2,#,#,#,6,#, then through these two counter examples,

If the root node is empty, there can be no more nodes behind,
And there cannot be three consecutive # signs.

So when we add or subtract the counter, if we encounter the # number, and the counter is already 0, and then subtracted to become a negative number, we directly return False, because in the correct sequence, any position i is in [ 0, i] The number of # numbers in the range is not greater than the number of digits.

When the loop is complete, we check whether the counter is 0 and also see whether the last character is # sign.

Code

Java

import java.util.Stack;

public class Verify_Preorder_Serialization_of_a_Binary_Tree {

    // https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/discuss/78551/7-lines-Easy-Java-Solution
    public class Solution_noStack {
        public boolean isValidSerialization(String preorder) {
            String[] nodes = preorder.split(",");
            int diff = 1; // if single node tree [root]
            for (String node: nodes) {
                if (--diff < 0) return false;
                if (!node.equals("#")) diff += 2;
            }
            return diff == 0;
        }
    }

    public class Solution {
        public boolean isValidSerialization(String preorder) {
            if (preorder == null || preorder.length() == 0) {
                return true;
            }

            String[] nodes = preorder.split(",");
            Stack<String> stack = new Stack<>();

            for (String node : nodes) {
                if (node.equals("#")) {
                    // after first while loop, current node can be deemed as #
                    while (!stack.isEmpty() && stack.peek().equals("#")) {
                        stack.pop(); // pop # in stack
                        if (stack.isEmpty()) { // should leave a number in stack
                            return false;
                        }

                        stack.pop(); // pop val with left-# and right-#   =>   repalce it with #
                    }
                }

                stack.push(node);
            }

            return stack.size() == 1 && stack.peek().equals("#");
        }
    }
}

331 - Verify Preorder Serialization of a Binary Tree

Question

Algorithm

Code

All Problems

All Solutions