1457. Pseudo-Palindromic Paths in a Binary Tree

• Binary tree를 root부터 leaf 까지 탐색했을 때의 경로를 라고 할 때 에 속하는 노드를 임의의 순서로 나열하여 회문(palindrome)을 만들 수 있는 경로의 수를 구하는 문제.

• 경로에 속한 노드를 자유롭게 배치할 수 있다면 회문을 만들기위한 조건은 아래와 같다.
• 경로에 속한 각 노드의 숫자 별 출현 빈도를 세었을 때 출현 빈도가 홀수인 숫자의 종류가 1개 이하여야 한다.
• 쉽게 생각하면 모든 숫자가 짝수 횟수만큼 출현했다면 문자열을 반으로 나누어 양쪽에 대칭으로 배치할 수 있을 것이다 (예: bbaaaabb).
• 만일 특정 숫자만 홀수 횟수 출현했다면 해당 문자를 한개만 가운데에 배치하고 나머지는 양쪽에 대칭으로 배치하면 된다 (예: bbaaabb).
• 하지만 홀수 횟수 출현한 숫자의 종류가 2개 이상이라면 위와 같이 대칭으로 배치할 수 있는 방법이 없으므로 회문을 만들 수 없다.

• 결국 경로마다 각 숫자별로 출현 빈도를 확인하고 홀수번 출현한 숫자의 수가 1개 이하인지 확인하면 된다.
• 노드의 숫자는 1 ~ 9가 올 수 있고 출현빈도가 홀수, 짝수 인지만 확인하면 된다.
• Integer의 1 ~ 9번째 bit를 각 숫자에 대응시켜 숫자가 출현할 때 마다 bit를 toggle한다.
• 최종적으로 1로 설정된 bit의 수를 세면 홀수번 출현한 숫자의 개수를 셀 수 있다.

class Solution {
    int traverse(TreeNode node, int state) {
        state ^= 1 << node.val;
        boolean isLeaf = node.left == null && node.right == null;
        if (isLeaf) {
            return Integer.bitCount(state) <= 1? 1 : 0;
        }
        int result = 0;
        if (node.left != null)
            result += traverse(node.left, state);
        if (node.right != null)
            result += traverse(node.right, state);
        return result;
    }
    
    public int pseudoPalindromicPaths (TreeNode root) {
        return traverse(root, 0);
    }
}