⚡Flashcard Drill➔
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

  1. Track the parity of each digit's count along the path as a 9-bit mask.
  2. XOR-ing 1 << node.val toggles the parity of that digit.
  3. At a leaf, the path is pseudo-palindromic exactly when the mask has at most one bit set, i.e. mask & (mask - 1) == 0.
  4. 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 the mask & (mask - 1) == 0 trick, 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems