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.
1#include <unordered_set>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11class Solution {
12public:
13 int pseudoPalindromicPaths(TreeNode* root) {
14 unordered_set<int> counts;
15 return dfs(root, counts);
16 }
17
18 int dfs(TreeNode* node, unordered_set<int>& counts) {
19 if (!node) return 0;
20
21 if (counts.count(node->val)) {
22 counts.erase(node->val);
23 } else {
24 counts.insert(node->val);
25 }
26
27 if (!node->left && !node->right) {
28 return counts.size() <= 1 ? 1 : 0;
29 }
30
31 int leftPaths = dfs(node->left, counts);
32 int rightPaths = dfs(node->right, counts);
33
34 // Backtrack
35 if (counts.count(node->val)) {
36 counts.erase(node->val);
37 } else {
38 counts.insert(node->val);
39 }
40
41 return leftPaths + rightPaths;
42 }
43};The C++ solution employs a DFS approach and uses an unordered set to keep track of odd frequencies. As we traverse the tree, when we reach a leaf node, we check if the set's size is less than or equal to one, indicating a pseudo-palindromic path. We backtrack by undoing any changes to the set once we leave that node.
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.