1457. Pseudo-Palindromic Paths in a Binary Tree

Question

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.

Solution

用数组bin[]记录一个树枝上的节点。

回溯，遇到根节点则判断数组bin[]中是否只有0个或1个奇数的数字。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res;
    int[] bin;
    public int pseudoPalindromicPaths (TreeNode root) {
        res = 0;
        bin = new int[10];
        backtrack(root);
        return res;
    }
    
    private void backtrack(TreeNode root){
        if(root.left == null && root.right == null){
            bin[root.val]++;
            boolean flag = false;
            for(int i = 0; i < bin.length; i++){
                if(flag && (bin[i] & 1) == 1){
                    bin[root.val]--;
                    return;
                }
                else if((bin[i] & 1) == 1) flag = true;
            }
            res++;
            bin[root.val]--;
            return;
        }
        bin[root.val]++;
        if(root.left != null) backtrack(root.left);
        if(root.right != null) backtrack(root.right);
        bin[root.val]--;
    }
}