[Leetcode] Problem 1457 - Pseudo-Palindromic Paths in a Binary Tree

Posted on | In ,

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

No.1

0s5Z26.png

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).

No.2

0s5lad.png

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).

No.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.

Code

1
2
3
4
5
6
7
8
9
10
11
12
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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int pseudoPalindromicPaths(TreeNode root) {
    return dfs(root, 0);
}

private int dfs(TreeNode root, int state) {
    if (root == null)
        return 0;

    state ^= 1 << root.val;
    
    if (root.left == null && root.right == null) 
        return (state & (state - 1)) == 0 ? 1 : 0;

    return dfs(root.left, state) + dfs(root.right, state);
}