0331. Verify Preorder Serialization of a Binary Tree

https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree

Description

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 = "9,3,4,#,#,1,#,#,2,#,6,#,#"
**Output:** true

Example 2:

**Input:** preorder = "1,#"
**Output:** false

Example 3:

**Input:** preorder = "9,#,#,1"
**Output:** false

Constraints:

• 1 <= preorder.length <= 104

• preorder consist of integers in the range [0, 100] and '#' separated by commas ','.

ac1: preorder offset each node

https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/discuss/78566/Java-intuitive-22ms-solution-with-stack/83378

• See number, push to stack;

• See #:

  • stack top is number, it's left null child, push to stack;

  • stack top is #, it's right null child. Cancel a subtree by pop() twice. Keep doing this.

• Finally, only one # is left in the stack.

class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] nodes = preorder.split(",");
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < nodes.length; i++) {
            if ("#".equals(nodes[i])) {
                while (!stack.isEmpty() && stack.peek().equals("#")) {
                    stack.pop();
                    if (stack.isEmpty()) return false;
                    stack.pop();
                }
            }
            stack.push(nodes[i]);
        }

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

ac2: count leaves and non-leaves

https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/discuss/78551/7-lines-Easy-Java-Solution/83320

If we treat null's as leaves, then the binary tree will always be full. A full binary tree has a good property that # of leaves = # of nonleaves + 1

class Solution {
    public boolean isValidSerialization(String preorder) {
        int leaves = 0, nonLeaves = 0;
        for (String s : preorder.split(",")) {
            // Got a complete full tree before running out of nodes, which is invalid.
            if (leaves == nonLeaves + 1) return false;
            if ("#".equals(s)) {
                leaves++;
            } else {
                nonLeaves++;
            }
        }

        return leaves == nonLeaves + 1;
    }
}

ac3: count in-degree and out-degree

https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/discuss/78551/7-lines-Easy-Java-Solution

This is rediculous for interview.

class Solution {
    public boolean isValidSerialization(String preorder) {
        int in = 0;
        int out = 1; // This is to account for root node, which has no in-degree.
        for (String s : preorder.split(",")) {
            in++;
            // In-degree > out-degree: the new node cannot link to a parent node(No one is providing out-degree for it).
            if (in > out) return false;

            if (!"#".equals(s)) {
                out += 2;
            }
        }

        return in == out;
    }
}