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:
- The given binary tree will have between
1
and10^5
nodes. - Node values are digits from
1
to9
.
Solution: Counting
At most one number can occur odd times.
Time complexity: O(n)
Space complexity: O(n) / stack size
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua class Solution { public: int pseudoPalindromicPaths (TreeNode* root) { vector<int> counts(10); function<int(TreeNode*)> dfs = [&](TreeNode* node) { if (!node) return 0; ++counts[node->val]; int c = 0; if (!node->left && !node->right) { int odds = 0; for (int i = 1; i <= 9; ++i) if (counts[i] & 1) ++odds; if (odds <= 1) c = 1; } int l = dfs(node->left); int r = dfs(node->right); --counts[node->val]; return c + l + r; }; return dfs(root); } }; |
Use a binary string to represent occurrences of each number (even: 0 / odd: 1), we can use xor to flip the bit.
C++
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua class Solution { public: int pseudoPalindromicPaths(TreeNode* root, int s = 0) { if (!root) return 0; s ^= (1 << root->val); if (!root->left && !root->right) return __builtin_popcount(s) <= 1; return pseudoPalindromicPaths(root->left, s) + pseudoPalindromicPaths(root->right, s); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment