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:
[1, 105].1 <= Node.val <= 9This approach involves traversing the tree using a depth-first search (DFS) and maintaining a frequency count of digits encountered. We check if the frequency count allows a pseudo-palindromic path by ensuring there is at most one digit with an odd count.
The solution uses a DFS approach where a 'path' is represented using a bit mask, with each bit position corresponding to the digits 1 to 9. As we traverse to each node, we toggle the corresponding bit for the node's value. At leaf nodes, we check if the bit mask represents a pseudo-palindromic path by ensuring that only one bit is set (i.e., path & (path - 1) == 0).
C++
Time Complexity: O(N), where N is the number of nodes in the tree, since we visit each node once.
Space Complexity: O(H), where H is the height of the tree. This is due to the recursion stack used by DFS.
This approach maintains an array to count the frequencies of digits from 1 to 9 along the path. We use DFS to explore all paths from the root to leaves and check each path for pseudo-palindromic properties by counting the odd frequencies in the array.
The Java solution uses an integer array count to manage digit frequencies. During the DFS traversal, digits are incremented or decremented in the array. At leaf nodes, if there is at most one digit with an odd frequency, it contributes to the pseudo-palindromic path count.
JavaScript
Time Complexity: O(N), as it processes each node once.
Space Complexity: O(H), where H is the height of the tree, due to recursion and the constant-size count array.
| Approach | Complexity |
|---|---|
| Depth-First Search with Frequency Counting | Time Complexity: O(N), where N is the number of nodes in the tree, since we visit each node once. |
| Depth-First Search with Path Count Array | Time Complexity: O(N), as it processes each node once. |
Pseudo-Palindromic Paths in a Binary Tree - Leetcode 1457 - Python • NeetCodeIO • 16,476 views views
Watch 9 more video solutions →Practice Pseudo-Palindromic Paths in a Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor