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
Solutions
Solution 1: DFS + Bit Manipulation
A path is a pseudo-palindromic path if and only if the number of nodes with odd occurrences in the path is $0$ or $1$.
Since the range of the binary tree node values is from $1$ to $9$, for each path from root to leaf, we can use a $10$-bit binary number $mask$ to represent the occurrence status of the node values in the current path. The $i$th bit of $mask$ is $1$ if the node value $i$ appears an odd number of times in the current path, and $0$ if it appears an even number of times. Therefore, a path is a pseudo-palindromic path if and only if $mask \&(mask - 1) = 0$, where $\&$ represents the bitwise AND operation.
Based on the above analysis, we can use the depth-first search method to calculate the number of paths. We define a function $dfs(root, mask)$, which represents the number of pseudo-palindromic paths starting from the current $root$ node and with the current state $mask$. The answer is $dfs(root, 0)$.
The execution logic of the function $dfs(root, mask)$ is as follows:
If $root$ is null, return $0$;
Otherwise, let $mask = mask \oplus 2^{root.val}$, where $\oplus$ represents the bitwise XOR operation.
If $root$ is a leaf node, return $1$ if $mask \&(mask - 1) = 0$, otherwise return $0$;
If $root$ is not a leaf node, return $dfs(root.left, mask) + dfs(root.right, mask)$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 91011121314151617
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defpseudoPalindromicPaths(self,root:Optional[TreeNode])->int:defdfs(root:Optional[TreeNode],mask:int):ifrootisNone:return0mask^=1<<root.valifroot.leftisNoneandroot.rightisNone:returnint((mask&(mask-1))==0)returndfs(root.left,mask)+dfs(root.right,mask)returndfs(root,0)
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcpseudoPalindromicPaths(root*TreeNode)int{vardfsfunc(*TreeNode,int)intdfs=func(root*TreeNode,maskint)int{ifroot==nil{return0}mask^=1<<root.Valifroot.Left==nil&&root.Right==nil{ifmask&(mask-1)==0{return1}return0}returndfs(root.Left,mask)+dfs(root.Right,mask)}returndfs(root,0)}