二叉树中的伪回文路径

难度: Medium

给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。

请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。

示例 1：

输入：root = [2,3,1,3,1,null,1]
输出：2 
解释：上图为给定的二叉树。总共有 3 条从根到叶子的路径：红色路径 [2,3,3] ，绿色路径 [2,1,1] 和路径 [2,3,1] 。
     在这些路径中，只有红色和绿色的路径是伪回文路径，因为红色路径 [2,3,3] 存在回文排列 [3,2,3] ，绿色路径 [2,1,1] 存在回文排列 [1,2,1] 。

示例 2：

输入：root = [2,1,1,1,3,null,null,null,null,null,1]
输出：1 
解释：上图为给定二叉树。总共有 3 条从根到叶子的路径：绿色路径 [2,1,1] ，路径 [2,1,3,1] 和路径 [2,1] 。
     这些路径中只有绿色路径是伪回文路径，因为 [2,1,1] 存在回文排列 [1,2,1] 。

示例 3：

输入：root = [9]
输出：1

提示：

给定二叉树的节点数目在范围 [1, 10⁵] 内
1 <= Node.val <= 9

Submission

运行时间: 296 ms

内存: 45.5 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pseudoPalindromicPaths (self, root: Optional[TreeNode], mask=0) -> int:
        if root is None:
            return 0
        mask ^= 1 << root.val
        if root.left is root.right:
            return 1 if mask & (mask - 1) == 0 else 0
        return self.pseudoPalindromicPaths(root.left, mask) + \
            self.pseudoPalindromicPaths(root.right, mask)

Explain

该题解采用的是深度优先搜索（DFS）的方法。在递归过程中，使用一个整数mask来跟踪路径上节点值出现的奇偶次数。mask的每一位对应一个数字（1-9），如果某一位是1，则表示对应的数字出现了奇数次，如果是0，则表示出现了偶数次。当到达叶子节点时，检查mask中1的个数，如果小于等于1，则说明这条路径是伪回文的。

时间复杂度: O(n)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pseudoPalindromicPaths (self, root: Optional[TreeNode], mask=0) -> int:
        if root is None:
            return 0
        # XOR operation to toggle the bit corresponding to the current node's value
        mask ^= 1 << root.val
        # Check if the current node is a leaf node
        if root.left is root.right:
            # Check if at most one bit is set in mask (which means at most one odd occurrence)
            return 1 if mask & (mask - 1) == 0 else 0
        # Recur for left and right subtrees and sum the results
        return self.pseudoPalindromicPaths(root.left, mask) + \
            self.pseudoPalindromicPaths(root.right, mask)

Explore

在递归函数中，整数`mask`被用作一个位掩码，其中每个位代表一个数字（1-9）。对于二叉树中的每个节点，我们使用异或运算（XOR）来更新`mask`。具体地，`mask ^= 1 << root.val`操作会翻转与节点值对应的位。如果该位原来是0（表示偶数次），它将变为1（表示奇数次），如果原来是1，则变回0。这种方法能有效地在每个节点处更新其值的出现频率（奇数次或偶数次），而不需要额外的空间来存储每个数字的计数。

在回文结构中，最多只能有一个数字出现奇数次，其他必须都是偶数次。`mask & (mask - 1)`操作的作用是清除最低位的1，如果执行这个操作后结果为0，意味着在`mask`中只有一个1或者没有1。这表明至多只有一个数字出现了奇数次。因此，当`mask & (mask - 1) == 0`成立时，这条路径上的数字可以重新排列成一个回文结构。

使用位运算而不是哈希表或数组的主要原因是效率和空间利用。位运算提供了一种极其高效的方式来跟踪数字的出现次数，尤其是当数据范围有限（如1到9）时。位运算相较于哈希表或数组，具有更低的空间复杂度和更快的访问及更新速度。此外，位运算可以直接利用CPU指令，进一步加速运算。

将节点值限制在1到9范围内是基于问题描述和位掩码方法的设计。这种限制简化了位掩码的使用，因为只需要9位就可以跟踪所有可能的数字。如果节点值超出这个范围，当前的位掩码方法将不再适用，我们需要采用更复杂的数据结构如哈希表或数组来跟踪出现次数。这样的改动会增加空间复杂度和可能影响性能。因此，这个限制确实降低了算法的通用性，但是对于题目给定的特定情况是有效的。