Binary Tree     Bit Manipulation     Breadth-First Search     C++     Depth-First Search     Medium     Tree    

Problem Statement:

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.

 

Example 1:

Input: root = [2,3,1,3,1,null,1]
Output: 2 
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 2:

Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1 
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 3:

Input: root = [9]
Output: 1

 

Constraints:

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

Solution:

Given an array, how do we know if it can be rearranged into a palindrome? The answer is it can have at most one member with odd frequency. This will be the center. If there are no members with odd frequency then we can just put half of each member on each side.

So, given an array of frequencies of unique elements, we can apply the following test:

 
bool isPalindrome(vector<int> frequencies)
{
    bool foundOdd=false;
    for(int f: frequencies) if(f%2)
    {
        if(foundOdd) return false; 
        else foundOdd=true;
    }
    return true;
}

We can collect the frequencies and apply this test at each leaf node. To collect the frequencies of root node to leaf node, we use DFS.

 
class Solution {
    int res = 0;
public:
    bool isPalindrome(vector<int> frequencies)
    {
        bool foundOdd=false;
        for(int f: frequencies) if(f%2)
        {
            if(foundOdd) return false; 
            else foundOdd=true;
        }
        return true;
    }
    void dfs(TreeNode* root, vector<int>&frequencies)
    {
        if(!root) return;
        frequencies[root->val]++;
        if(!root->left && !root->right) res+=isPalindrome(frequencies);
        dfs(root->left, frequencies);
        dfs(root->right, frequencies);
        frequencies[root->val]--;
    }
    int pseudoPalindromicPaths (TreeNode* root) 
    {
        vector<int>frequencies(10,0);
        dfs(root,frequencies);        
        return res;
    }
};