题目描述
思路解析动画文字版
记住「能重排成回文 = 出现奇数次的数字最多一个」，下面沿每条根到叶路径数一遍奇偶。
准备 · 从根出发：开局路径为空、所有数字出现 0 次(偶)。DFS 从根一路走到每个叶子,沿途翻转经过数字的奇偶。
下行 · 访问 根：走到「根」(值 2,紫色)。把数字 2 的出现次数奇偶翻一下。它还有孩子,继续往下走。
下行 · 访问 根·左：走到「根·左」(值 3,紫色)。把数字 3 的出现次数奇偶翻一下。它还有孩子,继续往下走。
下行 · 访问 根·左·左：走到「根·左·左」(值 3,紫色)。把数字 3 的出现次数奇偶翻一下。它还有孩子,继续往下走。
下行 · 访问 根·左·左·左：走到「根·左·左·左」(值 1,紫色)。把数字 1 的出现次数奇偶翻一下。它没有孩子,是叶子,马上判定这条路径。
叶子判定 · 根·左·左·左：到达叶子「根·左·左·左」。出现奇数次的数字有 2 个(1、2),超过 1 个,✗ 不是伪回文,该叶变红,计数不变(0)。
回溯 · 离开 根·左·左·左：「根·左·左·左」这边走完了,回溯:把它从路径里去掉、数字 1 的奇偶翻回原样(标蓝表示已处理),这一层没有别的孩子了,继续向上一层回溯。
回溯 · 离开 根·左·左：「根·左·左」这边走完了,回溯:把它从路径里去掉、数字 3 的奇偶翻回原样(标蓝表示已处理),回到父节点,继续走还没走的另一边。
下行 · 访问 根·左·右：走到「根·左·右」(值 1,紫色)。把数字 1 的出现次数奇偶翻一下。它还有孩子,继续往下走。
下行 · 访问 根·左·右·右：走到「根·左·右·右」(值 3,紫色)。把数字 3 的出现次数奇偶翻一下。它没有孩子,是叶子,马上判定这条路径。
叶子判定 · 根·左·右·右：到达叶子「根·左·右·右」。出现奇数次的数字有 2 个(1、2),超过 1 个,✗ 不是伪回文,该叶变红,计数不变(0)。
回溯 · 离开 根·左·右·右：「根·左·右·右」这边走完了,回溯:把它从路径里去掉、数字 3 的奇偶翻回原样(标蓝表示已处理),这一层没有别的孩子了,继续向上一层回溯。
回溯 · 离开 根·左·右：「根·左·右」这边走完了,回溯:把它从路径里去掉、数字 1 的奇偶翻回原样(标蓝表示已处理),这一层没有别的孩子了,继续向上一层回溯。
回溯 · 离开 根·左：「根·左」这边走完了,回溯:把它从路径里去掉、数字 3 的奇偶翻回原样(标蓝表示已处理),回到父节点,继续走还没走的另一边。
下行 · 访问 根·右：走到「根·右」(值 1,紫色)。把数字 1 的出现次数奇偶翻一下。它还有孩子,继续往下走。
下行 · 访问 根·右·左：走到「根·右·左」(值 2,紫色)。把数字 2 的出现次数奇偶翻一下。它没有孩子,是叶子,马上判定这条路径。
叶子判定 · 根·右·左：到达叶子「根·右·左」。这条路径出现奇数次的数字只有 1 一个(≤1),✓ 是伪回文,该叶变绿,计数 +1 = 1。
回溯 · 离开 根·右·左：「根·右·左」这边走完了,回溯:把它从路径里去掉、数字 2 的奇偶翻回原样(标蓝表示已处理),回到父节点,继续走还没走的另一边。
下行 · 访问 根·右·右：走到「根·右·右」(值 1,紫色)。把数字 1 的出现次数奇偶翻一下。它没有孩子,是叶子,马上判定这条路径。
叶子判定 · 根·右·右：到达叶子「根·右·右」。这条路径出现奇数次的数字只有 2 一个(≤1),✓ 是伪回文,该叶变绿,计数 +1 = 2。
回溯 · 离开 根·右·右：「根·右·右」这边走完了,回溯:把它从路径里去掉、数字 1 的奇偶翻回原样(标蓝表示已处理),这一层没有别的孩子了,继续向上一层回溯。
回溯 · 离开 根·右：「根·右」这边走完了,回溯:把它从路径里去掉、数字 1 的奇偶翻回原样(标蓝表示已处理),这一层没有别的孩子了,继续向上一层回溯。
回溯 · 离开 根：「根」这边走完了,回溯:把它从路径里去掉、数字 2 的奇偶翻回原样(标蓝表示已处理)。根节点退出,整棵树遍历结束,准备汇总答案。
完成：全部路径走完,绿色的两片叶子(根·右·左、根·右·右)对应的路径是伪回文,答案 2。判定全靠「出现奇数次的数字 ≤ 1」。
边界先想清:单节点必是、0 个奇数也行、2 个奇数不行。
面试重点:奇偶用位掩码的动机,以及传参 vs 全局的回溯差异。
参考代码
from typing import Optionalclass TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass Solution: def pseudoPalindromicPaths(self, root: Optional[TreeNode]) -> int: def dfs(node, mask): if not node: return 0 mask ^= 1 << node.val if not node.left and not node.right: return 1 if mask & (mask - 1) == 0 else 0 return dfs(node.left, mask) + dfs(node.right, mask) return dfs(root, 0)复杂度
- 时间：O(n)，每个节点访问一次
- 空间：O(h)，递归栈深 = 树高 h;掩码 O(1)
易错点
面试追问把动画讲成自己的话
追问为什么用掩码而不用一个长度 10 的计数数组？
追问回溯时这道题为什么可以「不显式还原」？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
从一个节点到另一个节点每一步的方向
LeetCode 2096 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题