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.
1function TreeNode(val, left, right) {
The JavaScript solution uses DFS and utilizes a fixed-length array to track frequencies of node values. Paths are checked against the pseudo-palindromic condition at each leaf by counting array elements with odd frequencies, which needs to be at most one. The frequency array is updated in a backtracking manner as the traversal returns from recursive calls.