[LeetCode] 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

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - Pseudo-Palindromic Paths in a Binary Tree

문제 유형 : 백트래킹, dfs

문제 난이도 : Medium

 

 

문제

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.

 

1에서 9의 값을 가진 노드들로 구성된 이진 트리가 주어진다.

숫자들을 재배열하여 팰린드롬을 만들 수 있으면, 가짜-팰린드롬이라고 한다.

루트에서 각 리프노드까지 가짜-팰린드롬이 나오는 개수를 구하시오.

 

 

풀이

dfs+ 백트래킹으로 풀 수 있다.

map 자료구조로 각 숫자의 개수를 방문하면서 저장한다.

백트래킹으로 이번 노드의 방문이 끝나면, map에서 하나 빼주면 된다.

만약, 현재 노드가 리프노드라면, 가짜-팰린드롬인지 확인하고, 개수를 1 추가하면 된다.

 

가짜-리프노드인지 확인하는 방법은, 홀수 개의 요소의 수가 1 이하를 만족하면 된다.

dfs가 종료되면 개수를 반환한다.

 

코드

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    unordered_map<int, int> mp;
    int paths;
public:
// 팰린드롬 검사
    bool isPalindrome() {
        int oddCount = 0;
        for(const auto &m : mp) {
            if(m.second%2) oddCount++;
            if(oddCount > 1) return false;
        }
        return true;
    }

// dfs
    void solve(TreeNode* node) {
    // 만약 리프라면, 팰린드롬인지 확인 후 개수 1 증가
        if(!(node -> right) && !(node -> left)) {
            if(isPalindrome()) paths++;
            return;
        }
        
        // 왼쪽 자식이 있으면, 왼쪽으로 백트래킹
        if(node -> left) {
            mp[node -> left -> val]++;
            solve(node -> left);
            mp[node -> left -> val]--;
        }
        
        // 오른쪽 자식이 있으면, 오른쪽으로 백트래킹
        if(node -> right) {
            mp[node -> right -> val]++;
            solve(node -> right);
            mp[node -> right -> val]--;
        }
    }
    int pseudoPalindromicPaths (TreeNode* root) {
    	// 변수 초기화 및 루트 값 넣기, 탐색 시작
        paths = 0;
        mp[root -> val]++;
        solve(root);
        return paths;
    }
};