Formatted question description: https://leetcode.ca/all/1457.html

1457. Pseudo-Palindromic Paths in a Binary Tree (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.

 

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 given binary tree will have between 1 and 10^5 nodes.
  • Node values are digits from 1 to 9.

Related Topics:
Bit Manipulation, Tree, Depth-first Search

Solution 1.

A path is pseudo-palindromic if there is at most 1 digit with odd occurrences in the path.

We can use pre-order traversal and keep track of the count of occurrences of digits in cnt array.

If we meet a leaf node and there is at most 1 digit with odd occurrences, we increment the answer.

// OJ: https://leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree/

// Time: O(N)
// Space: O(H)
class Solution {
    int cnt[10] = {}, ans = 0;
    void dfs(TreeNode *root) {
        if (!root) return;
        cnt[root->val]++;
        if (!root->left && !root->right) {
            int c = 0;
            for (int i = 1; i < 10; ++i) {
                c += cnt[i] % 2;
                if (c >= 2) break;
            }
            if (c < 2) ++ans;
        }
        dfs(root->left);
        dfs(root->right);
        cnt[root->val]--;
    }
public:
    int pseudoPalindromicPaths (TreeNode* root) {
        dfs(root);
        return ans;
    }
};

Another variation that doesn’t require the O(9) check of the count of odd occurrences.

// OJ: https://leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree/

// Time: O(N)
// Space: O(H)
class Solution {
    int cnt[10] = {}, odd = 0, ans = 0;
    void dfs(TreeNode *root) {
        if (!root) return;
        cnt[root->val]++;
        int diff = cnt[root->val] % 2 ? 1 : -1;
        odd += diff;
        ans += !root->left && !root->right && odd < 2;
        dfs(root->left);
        dfs(root->right);
        odd -= diff;
        cnt[root->val]--;
    }
public:
    int pseudoPalindromicPaths (TreeNode* root) {
        dfs(root);
        return ans;
    }
};

Java

/**
 * 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 {
    public int pseudoPalindromicPaths (TreeNode root) {
        if (root == null)
            return 0;
        if (root.left == null && root.right == null)
            return 1;
        int count = 0;
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<String> pathQueue = new LinkedList<String>();
        nodeQueue.offer(root);
        pathQueue.offer(String.valueOf(root.val));
        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            String path = pathQueue.poll();
            TreeNode left = node.left, right = node.right;
            if (left == null && right == null) {
                if (canFormPalindrome(path))
                    count++;
            } else {
                if (left != null) {
                    StringBuffer sb = new StringBuffer(path);
                    sb.append(left.val);
                    nodeQueue.offer(left);
                    pathQueue.offer(sb.toString());
                }
                if (right != null) {
                    StringBuffer sb = new StringBuffer(path);
                    sb.append(right.val);
                    nodeQueue.offer(right);
                    pathQueue.offer(sb.toString());
                }
            }
        }
        return count;
    }

    public boolean canFormPalindrome(String path) {
        Set<Character> set = new HashSet<Character>();
        int length = path.length();
        for (int i = 0; i < length; i++) {
            char c = path.charAt(i);
            if (!set.add(c))
                set.remove(c);
        }
        return set.size() <= 1;
    }
}

All Problems

All Solutions