[leetcode #331] Verify Preorder Serialization of a Binary Tree

Problem

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

Idea

SRT를 타고 고향에서 성남으로 올라가는 중 풀었다. Tree를 만들지 않고 주어진 string이 binary tree의 pre-order인지 판별하는 문제다. 두 개의 stack을 활용해서 문제를 풀었는데 결과가 심히 좋지 않아 더 나은 방법이 (당연히) 있을 것 같다.

두 개의 stack을 사용하는데, 한 stack에 노드를 넣고, 다른 stack에는 노드가 자식노드를 가지고 있는지 확인할 수 있는 flag를 저장했다. 이렇게 하면 숫자나 null이 나왔을 때 자식노드를 가지고 있으면 노드와 flag를 꺼내고 자식노드가 없으면 자식노드를 가지고 있다는 flag를 stack에 저장한다.

노드를 저장할 때 null이 아닌 경우만 flag와 노드를 저장하고, null일 경우는 앞에서 설명한 과정만 수행하면 된다.

또한 숫자가 한 자리가 아니라 100까지 가능하므로 이를 고려해야 한다. 나같은 경우는 노드가 가지고 있는 값이 전혀 쓰이지 않으므로 이전 문자가 숫자일 경우 다음 문자로 넘어가게 했다.

알고리즘은 다음과 같다.

1. 노드를 저장하는 stack과 자식 노드 유무를 확인하는 flag stack을 만든다.
2. 첫 번째 문자가 null일 경우
   a. 문자열의 길이가 1이면 true를 리턴한다
   b. 문자열의 길이가 1이 아니면 false를 리턴한다.
3. 첫 번째 문자를 stack에 저장하고 자식 노드가 없다는 flag를 stack에 저장한다.
4. 문자열을 탐색한다.
   a. 이전문자가 ','가 아닐 경우 다음 문자로 넘어간다.
   b. 노드 stack이 비었을 경우 false를 리턴한다.
   c. flag를 확인하여 자식노드가 없으면 flag를 자식노드가 있음으로 바꿔주고, 자식노드가 있으면 노드 stack 가장 위 노드를 꺼낸다. flag stack의 가장 위 flag도 꺼낸다.
   d. 노드가 null이 아닌 경우 노드 stack에 노드를, flag stack에 자식 노드가 없다는 flag를 넣어준다.
5. 노드 stack이 비었을 경우 true를 리턴하고, 아닐 경우 false를 리턴한다.

Solution

class Solution {
    public boolean isValidSerialization(String preorder) {
        Stack<Character> numbers = new Stack<Character>();
        Stack<Boolean> hasNode = new Stack<Boolean>();

        char prevChar = ',';
        char start = preorder.charAt(0);
        if (start == '#') {
            if (preorder.length() == 1)
                return true;

            return false;
        }

        numbers.push(start);
        hasNode.push(false);

        for (int i=1; i < preorder.length(); i++) {
            char character = preorder.charAt(i);
            if (character == ',' || prevChar != ',') {
                prevChar = character;
                continue;
            }
            prevChar = character;
   
            if (numbers.isEmpty())
                return false;

            if (!hasNode.peek()) {
                hasNode.pop();
                hasNode.push(true);
            } else {
                numbers.pop();
                hasNode.pop();
            }
   
            if (character != '#') {
                numbers.push(character);
                hasNode.push(false);
            }
        }

        return numbers.isEmpty();
    }
}

보여주기 부끄러운 결과를 공개합니다!

Reference

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