[2024] Day24. 1457. Pseudo-Palindromic Paths in a Binary Tree

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 1월 24일 (수)
Leetcode daily problem

1457. Pseudo-Palindromic Paths in a Binary Tree

https://leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree/description/?envType=daily-question&envId=2024-01-24

Problem

이진 트리에서 루트에서 리프 노드까지의 경로 중에서 회문(palindrome)이 되는 수를 찾는다.
여기서 회문은 앞으로 읽든 뒤로 읽든 동일한 문자열을 의미한다. 예를 들면 기러기, 스위스, 토마토, 우영우
이때, 주어진 이진 트리의 각 노드에는 1에서 9까지의 숫자가 할당되어 있다. 이진 트리를 탐색하면서 회문의 개수를 반환한다.

Solution

dfs

먼저 0~9까지의 숫자가 노드 안에 해당하므로
temp라는 사이즈가 10인 배열을 0혹은 False로 할당한다.

깊이 탐색을 통해서 이진 트리를 탐색해 나가고,
탐색하는 과정에서 현재 노드의 값을 기준으로 tmp 리스트의 해당 인덱스를 업데이트한다.
즉, 만약 tmp[node.val]가 0이었다면 1로, 1이었다면 0으로 변경한다. 현재 경로에서 각 숫자의 등장 횟수를 추적하는 역할이다.

해당 과정에서 left, right 노드가 없는 즉, 마지막 터미널 노드에 다다랐을 때 리스트의 합이 1 이하인 경우는 pseudo-palindromic 경로라고 판단할 수 있다.
pseudo-palindromic 경로에서는 최대 하나의 홀수 빈도를 가진 숫자만 허용되기 때문이다.

펠린드롬(회문)은 앞 뒤로 문자열이 같아야 하는데, 탐색하는 과정에서 빈도수에 따라 0이 1로 1이 0으로 바뀌면서 중심이 되는 문자열이 최대 하나까지만 나와야 펠린드롬이 될 수 있기 때문이다.

예를들어 21312 가 나왔을 경우 2는 0->1->0
1 또한 0->1->0, 3은 0->1 이기 때문이다.

이 코드의 핵심 아이디어는 DFS를 사용하여 트리를 순회하면서 각 경로에서 숫자의 등장 횟수를 추적하고, 각 리프 노드에서 pseudo-palindromic 경로를 찾아낸다는 것이다.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:

        def dfs(node, tmp):
            if not node:
                return

            tmp[node.val] = not tmp[node.val]
            
            if not node.left and not node.right:
                if sum(tmp) <=1:
                    nonlocal ans
                    ans +=1
            else:
                dfs(node.left, tmp)
                dfs(node.right, tmp)
            
            tmp[node.val] = not tmp[node.val]
        
        tmp = [0] * 100
        ans = 0
        dfs(root, tmp)
        return ans  

Complexicity

시간 복잡도

dfs로 각 노드를 한번씩 방문하므로, 모든 노드에 대한 탐색 시간은 O(N) 이다.

공간 복잡도

dfs로 탐색하므로, 최대 트리 높이만큼의 스택 공간이 필요하다. 이진 트리의 최대 높이는 logn 이므로 총 공간복잡도는 O(logn)이다. 참고로 tmp 리스트는 상수크기이므로 추가적인 공간을 차지 하지 않는다. tmp(10)

---

비트 연산과 같이 풀던데, 아직 비트 연산은 익숙하지 않아서
그나마 이해하기 쉬운 dfs로만 푸는 로직으로 이해했다.
ans 변수를 nonlocal로 선언하여 함수 외부의 ans 변수를 참조할 수 있도록 해야한다.