[리트코드] 1457. 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.

root node .. terminal node 에서의 원소 리스트를 조합해 palindrome이 되는 경우의 수를 세는 문제이다.

풀이

백트래킹 방법으로 , 단말 노드까지 탐색한다.
단말 노드에 도달할 경우. 루트 노드에서 터미널 노드까지 원소들의 개수의 홀,짝을 계산하여 홀수가 1 이하인 경우 카운팅하였다.

코드

class Solution {
    int visit[] ;
    int ans;
    public int pseudoPalindromicPaths (TreeNode root) {
        visit = new int[10];
        ans = 0;
        
        helper(root, 0, 0);
        return ans;
    }
    
    public void helper(TreeNode root,int even, int odd){
        if(root == null){
            return;
        }
        visit[root.val]++;
        int rootVal = visit[root.val];
        
        //if odd
        if(rootVal % 2 != 0){
            odd++;
        }else{ //if even.
            odd--;
            even++;
        }
        if(root.left == null && root.right == null){
            if(odd<=1) ans++;
                    visit[root.val]= visit[root.val]-1;
            return;
        }
        helper(root.left, even, odd);
        helper(root.right, even, odd);
        visit[root.val]= visit[root.val]-1;
       // System.out.println("현재 root.val "+root.val+"개수:"+visit[root.val]);
    }
}