[LeetCode] 1457 | Pseudo-Palindromic Paths in an Binary Tree | Python

---

문제 링크: https://leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree/

---

문제

Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

---

조건

• The number of nodes in the tree is in the range [1, $10^5$].
• 1 <= Node.val <= 9

---

내 풀이

root에서 시작해서 가장 끝에 있는 leaf까지의 val의 수를 세서 count에 저장한다.

현재 leaf가 가장 끝에 있는지 확인하는 방법은 root.left와 root.right이 둘 다 존재하지 않음을 확인하는 것이다.

가장 끝에 있는 leaf에 도달했을 때 count 안의 value들을 확인한 후, 해당 value의 값이 홀수인 것이 하나 이하면 ans에 1을 추가한다.

왜냐하면 value의 값이 홀수인 것이 하나일 때만 palindrome이 가능하기 때문이다.

---

코드

# 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 search(root, count):
            nonlocal ans
            if not root:
                return
            
            count[root.val] += 1
            if not root.left and not root.right:
                has_odd = 0
                for val in count.values():
                    if val%2 == 1:
                        has_odd += 1
                if has_odd <= 1:
                    ans += 1
                    
            search(root.left, count)
            search(root.right, count)
            count[root.val] -= 1
                
        count = defaultdict(int)
        ans = 0
        search(root, count)
        
        return ans