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.
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.