NeetCode #460LC-1457MediumTrees
← Back to All Problems#460 · #1457 · Pseudo-Palindromic Paths in a Binary Tree(二叉树中的伪回文路径)
📌 Problem Statement & Constraints
Given the root of a binary tree where node values are digits
1..9, a path is pseudo-palindromic if at most one digit appears an odd number of times along it. Return the number of pseudo-palindromic paths from root to leaf. Constraints: the number of nodes is in [1, 10^5], 1 <= Node.val <= 9.💡 Core Algorithmic Approaches
- Track the parity of each digit's count along the path as a 9-bit mask.
- XOR-ing
1 << node.valtoggles the parity of that digit. - At a leaf, the path is pseudo-palindromic exactly when the mask has at most one bit set, i.e.
mask & (mask - 1) == 0. - The bitmask makes the parity tracking O(1) per node instead of maintaining a count array.
💻 Benchmark Python3 Implementation
class Solution:
def pseudoPalindromicPaths(self, root: Optional[TreeNode]) -> int:
self.res = 0
def dfs(node: Optional[TreeNode], mask: int) -> None:
if not node:
return
mask ^= 1 << node.val # toggle this digit's parity
if not node.left and not node.right:
# at most one odd count -> at most one bit set
if mask & (mask - 1) == 0:
self.res += 1
return
dfs(node.left, mask)
dfs(node.right, mask)
dfs(root, 0)
return self.res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node is visited once with O(1) bit operations.
💾 Space Complexity
O(h) for the recursion stack.
⚠️ Interview Pitfalls & Follow-ups
- Using
mask.bit_count() <= 1: correct but a bit slower than themask & (mask - 1) == 0trick, which tests exactly that. - Counting occurrences in an array and resetting on backtrack: workable, but the XOR mask is both faster and less error-prone.
- Checking the condition at every node: only root-to-leaf paths count.
- Forgetting to pass the mask by value: the mask must be local to each path, which the parameter passing ensures.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.