Sponsored
Sponsored
This 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.
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.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7def pseudoPalindromicPaths(root):
8 count = 0
9
10 def dfs(node, path):
11 nonlocal count
12 if not node:
13 return
14 path ^= (1 << node.val)
15 if not node.left and not node.right:
16 if path & (path - 1) == 0:
17 count += 1
18 else:
19 dfs(node.left, path)
20 dfs(node.right, path)
21
22 dfs(root, 0)
23 return countThe 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).
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.
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.
1class TreeNode {
2 int val;
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.