Question

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

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 <= 10⁴
preorder consist of integers in the range [0, 100] and '#' separated by commas ','.

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

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("#");
        }
    }
}

############

class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] strs = preorder.split(",");
        int diff = 1;
        for (String s : strs) {
            if (--diff < 0) {
                return false;
            }
            if (!s.equals("#")) {
                diff += 2;
            }
        }
        return diff == 0;
    }
}

class Solution {
public:
    bool isValidSerialization(string preorder) {
        istringstream in(preorder);
        vector<string> v;
        string t = "";
        int cnt = 0;
        while (getline(in, t, ',')) v.push_back(t);
        for (int i = 0; i < v.size() - 1; ++i) {
            if (v[i] == "#") {
                if (cnt == 0) return false;
                --cnt;
            } else ++cnt;
        }
        return cnt == 0 && v.back() == "#";
    }
};


class Solution {
public:
    bool isValidSerialization(string preorder) {
        int capacity = 1;
        preorder += ",";
        for (int i = 0; i < preorder.size(); ++i) {
            if (preorder[i] != ',') continue;
            if (--capacity < 0) return false;
            if (preorder[i - 1] != '#') capacity += 2;
        }
        return capacity == 0;
    }
};

'''
In this solution, we split the input string by comma to get a list of nodes. 
We then initialize the indegree counter to 1 for the root node, 
since the root has no incoming edges.

We then loop through the nodes and for each node, we decrease the indegree counter by 1. 
If the indegree counter becomes negative, 
it means that there are more incoming edges than expected, 
and the tree is invalid. In this case, we return False.

If the current node is not null (i.e., not '#'), 
we increase the indegree counter by 2 for its two children. 
This is because every non-null node has two children in a binary tree. 
Finally, we return True if the final indegree counter is 0, 
meaning that all incoming edges have been accounted for.
'''
class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        # Split the string by comma to get the list of nodes
        nodes = preorder.split(',')

        # since the root has no incoming edges
        indegree = 1

        for node in nodes:
            # Decrease the indegree for the current node
            indegree -= 1

            # If the indegree is negative, return False because the tree is invalid
            if indegree < 0:
                return False

            # If the current node is not null, increase the indegree by 2 for its children
            if node != '#':
                indegree += 2

        # Return True if the final indegree is 0
        return indegree == 0

############

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        if not preorder:
            return True
        
        nodes = preorder.split(",")
        stack = []
        
        for node in nodes:
            if node == "#":
                # after first while loop, current node can be deemed as #
                while stack and stack[-1] == "#":
                    stack.pop() # pop # in stack
                    if not stack: # should leave a number in stack
                        return False
                    
                    stack.pop() # pop val with left-# and right-#   =>   repalce it with #
            stack.append(node)
        
        return len(stack) == 1 and stack[0] == "#"

func isValidSerialization(preorder string) bool {
	stk := []string{}
	for _, s := range strings.Split(preorder, ",") {
		stk = append(stk, s)
		for len(stk) >= 3 && stk[len(stk)-1] == "#" && stk[len(stk)-2] == "#" && stk[len(stk)-3] != "#" {
			stk = stk[:len(stk)-3]
			stk = append(stk, "#")
		}
	}
	return len(stk) == 1 && stk[0] == "#"
}

331 - Verify Preorder Serialization of a Binary Tree

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions