[LeetCode] 331. Verify Preorder Serialization of a Binary Tree

문제 출처: https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/

Verify Preorder Serialization of a Binary Tree - LeetCode

---

문제

이진트리를 직렬화하는 한 가지 방법은 전위(Preorder) 순회를 사용하는 것이다. 널이 아닌 노드를 만날 때는 그 값 그대로 적고, 널 노드를 만날 때는 '#'과 같은 보조 값을 적는다.

예를 들어, 위의 이진트리를 직렬화한 값은 "9,3,4,#,#,1,#,#,2,#,6,#,#"이고, '#'은 널 노드를 표현한다.

 

쉼표로 각 값을 구분한 전위 순회 문자열이 주어지면, 문자열이 올바른 이진트리인지 아닌지를 판단하여 올바른 이진트리라면 true를 반환하라.

 

문자열에서 쉼표로 구분한 값은 정수이거나 '#'으로 표현된 널 포인터임이 보장된다.

 

입력 형태는 항상 유효한 형태임을 가정해도 된다.

• 예를 들어, "1,,3"과 같이 쉼표가 연속되어 나오는 경우는 주어지지 않는다.

주의: 트리를 재구축하는 방법은 사용하지 마라.

예제

Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true

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

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

---

풀이

문제에 대한 접근 방법을 생각하기 위해서 주어지는 문자열을 그대로 트리로 그려보았다. 여기서 '그대로'란 널 포인터를 뜻하는 문자 '#'까지 그림으로 표현한 것을 의미한다. ("9,3,4,#,#,1,#,#,2,#,6,#,#")

리프 노드의 패턴이 눈에 띈다. 당연하게도 리프 노드는 자식이 없는 노드이기 때문에 '#' 노드 두 개를 자식으로 갖게 된다. 이는 전위 순회에서도 "value,#,#"의 패턴으로 그대로 보이고 있다. ("9,3,4,#,#,1,#,#,2,#,6,#,#")

 

위 그림에서 리프 노드를 제거. 즉, '#' 노드로 치환하는 과정을 진행해보자. 정상적인 이진트리라면 다음과 같은 과정이 진행될 것이다.

이 과정을 주어지는 문자열에 그대로 적용해 볼 수 있다.

 

"9,3,4,#,#,1,#,#,2,#,6,#,#" => "9,3,#,#,2,#,#" => "9,#,#" => "#"

 

주어진 문자열에서 "정수,#,#" 의 패턴을 찾아 "#"으로 변경하는 과정을 반복적으로 적용한 것만으로 최종 "#" 문자열로 치환된 결과를 얻었다.

 

그렇다면 올바른 이진트리가 아니라면 어떻게 될까. 답이 false인 예제 "9,#,#,1"를 살펴보자. 

 

"9,#,#,1" => "#,1"

 

올바른 이진트리의 결과물과는 달리 "#" 이외의 문자가 붙어있음을 파악할 수 있다. 이와 같이 문자열에서 리프 노드의 패턴을 찾아 "#"으로 치환하는 것으로 올바른 이진트리의 문자열을 찾을 수 있다.

 

다음 코드는 정규표현식을 활용하여 리프 노드의 패턴을 찾아 문제를 해결한 코드이다.

var isValidSerialization = function(preorder) {
    const re = /(\d+,#,#)/g;
    while (re.test(preorder)) {
        preorder = preorder.replaceAll(re, '#');
    }
    
    return preorder === '#';
};

이처럼 리프 노드의 패턴을 찾기 위해서 정규표현식을 사용할 수도 있지만, 스택(Stack) 자료구조를 사용할 수도 있다. 다음과 같이 주어진 문자열을 분해하여 앞에서부터 값을 넣으면서 "정수,#,#" 패턴을 찾아내는 것이다.

스택을 사용하는 방식 또한 리프 노드를 발견하면, '#'으로 대체해서 넣고 다시 리프 노드를 찾아가는 과정을 반복한다. 이러한 반복을 하게 되면 결국 스택에 남아있는 노드는 # 노드뿐이어야 올바른 이진트리이다.

var isValidSerialization = function(preorder) {
    let nodes = preorder.split(',');
    let stack = [];
    for (let node of nodes) {
        stack.push(node);
        
        while (stack.length >= 3 && node == '#' && stack[stack.length-2] == '#' && stack[stack.length-3] !== '#') {
            stack.pop();
            stack.pop();
            stack[stack.length-1] = '#';
        }
    }
    
    return stack.length == 1 && stack[0] == '#';
};

 

Github: 331.js

GitHub - opwe37/Algorithm-Study