LeetCode 题解工作台
二叉树中的伪回文路径
给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「 伪回文 」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。 请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。 示例 1： 输入： root = [2,3,1,3,1,null,1] 输出： 2 解释：…
5
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
一条路径是伪回文路径，当且仅当该路径经过的节点值的出现次数为奇数的数字为 个或 个。 由于二叉树节点值的范围为 到 ，因此对于每一条从根到叶子的路径，我们可以用一个长度为 的二进制数 表示当前路径经过的节点值的出现状态，其中 的第 位为 ，表示当前路径上节点值 的出现次数为奇数，否则表示其出现次数为偶数。那么，如果一条路径是伪回文路径，需要满足 $mask \&(mask - 1)…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵二叉树，每个节点的值为 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, 105]内 1 <= Node.val <= 9
解题思路
方法一：DFS + 位运算
一条路径是伪回文路径，当且仅当该路径经过的节点值的出现次数为奇数的数字为 个或 个。
由于二叉树节点值的范围为 到 ，因此对于每一条从根到叶子的路径，我们可以用一个长度为 的二进制数 表示当前路径经过的节点值的出现状态，其中 的第 位为 ，表示当前路径上节点值 的出现次数为奇数，否则表示其出现次数为偶数。那么，如果一条路径是伪回文路径，需要满足 ，其中 表示按位与运算。
基于以上分析，我们可以使用深度优先搜索的方法计算路径数。我们定义一个函数 ，表示从当前 节点开始，且当前节点的状态为 的所有伪回文路径的个数。那么答案就是 。
函数 的执行逻辑如下：
如果 为空，则返回 ；
否则，令 ，其中 表示按位异或运算。
如果 是叶子节点，那么如果 ，返回 ，否则返回 ；
如果 不是叶子节点，返回 。
时间复杂度 ，空间复杂度 。其中 是二叉树的节点数。
# 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]) -> int:
def dfs(root: Optional[TreeNode], mask: int):
if root is None:
return 0
mask ^= 1 << root.val
if root.left is None and root.right is None:
return int((mask & (mask - 1)) == 0)
return dfs(root.left, mask) + dfs(root.right, mask)
return dfs(root, 0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N) since each node is visited once. Space complexity is O(H) due to recursion stack, where H is the height of the tree; bitmask storage is constant and does not affect asymptotic space. |
| 空间 | up to |
面试官常问的追问
外企场景- question_mark
DFS is a natural choice for path tracking in binary trees.
- question_mark
Bit manipulation efficiently tracks odd/even digit counts without full frequency arrays.
- question_mark
Leaf nodes are critical checkpoints for validating pseudo-palindromic paths.
常见陷阱
外企场景- error
Not flipping the bitmask correctly can miscount pseudo-palindromic paths.
- error
Failing to check the condition only at leaf nodes can include incomplete paths.
- error
Assuming multiple odd counts are acceptable will produce incorrect results.
进阶变体
外企场景- arrow_right_alt
Count pseudo-palindromic paths in an N-ary tree instead of a binary tree.
- arrow_right_alt
Return all the pseudo-palindromic paths instead of just the count.
- arrow_right_alt
Allow node values up to 15 and adapt the bitmask size accordingly.