LeetCode 1457中等树/DFS/位掩码
二叉树中的伪回文路径 图解题解
这道题到底在问什么
给定二叉树 root，节点值为 1~9。一条根到叶路径若其数字重排后可构成回文，则为伪回文。返回伪回文路径的数量。
- 输入
- root=[2,3,1,3,1,null,1]
- 输出
- 2
最优解：一步一步想明白
- 3记住「能重排成回文 = 出现奇数次的数字最多一个」，下面沿每条根到叶路径数一遍奇偶。
- 4路径空,掩码全 0开局路径为空、所有数字出现 0 次(偶)。DFS 从根一路走到每个叶子,沿途翻转经过数字的奇偶。
- 5根 的值 2,翻其奇偶走到「根」(值 2,紫色)。把数字 2 的出现次数奇偶翻一下。它还有孩子,继续往下走。
- 6根·左 的值 3,翻其奇偶走到「根·左」(值 3,紫色)。把数字 3 的出现次数奇偶翻一下。它还有孩子,继续往下走。
- 7根·左·左 的值 3,翻其奇偶走到「根·左·左」(值 3,紫色)。把数字 3 的出现次数奇偶翻一下。它还有孩子,继续往下走。
- 8根·左·左·左 的值 1,翻其奇偶走到「根·左·左·左」(值 1,紫色)。把数字 1 的出现次数奇偶翻一下。它没有孩子,是叶子,马上判定这条路径。
- 9奇数个数 2 > 1 → 不是到达叶子「根·左·左·左」。出现奇数次的数字有 2 个(1、2),超过 1 个,✗ 不是伪回文,该叶变红,计数不变(0)。
- 10撤销 根·左·左·左,掩码翻回「根·左·左·左」这边走完了,回溯:把它从路径里去掉、数字 1 的奇偶翻回原样(标蓝表示已处理),这一层没有别的孩子了,继续向上一层回溯。
- 11撤销 根·左·左,掩码翻回「根·左·左」这边走完了,回溯:把它从路径里去掉、数字 3 的奇偶翻回原样(标蓝表示已处理),回到父节点,继续走还没走的另一边。
- 12根·左·右 的值 1,翻其奇偶走到「根·左·右」(值 1,紫色)。把数字 1 的出现次数奇偶翻一下。它还有孩子,继续往下走。
- 13根·左·右·右 的值 3,翻其奇偶走到「根·左·右·右」(值 3,紫色)。把数字 3 的出现次数奇偶翻一下。它没有孩子,是叶子,马上判定这条路径。
- 14奇数个数 2 > 1 → 不是到达叶子「根·左·右·右」。出现奇数次的数字有 2 个(1、2),超过 1 个,✗ 不是伪回文,该叶变红,计数不变(0)。
- 15撤销 根·左·右·右,掩码翻回「根·左·右·右」这边走完了,回溯:把它从路径里去掉、数字 3 的奇偶翻回原样(标蓝表示已处理),这一层没有别的孩子了,继续向上一层回溯。
- 16撤销 根·左·右,掩码翻回「根·左·右」这边走完了,回溯:把它从路径里去掉、数字 1 的奇偶翻回原样(标蓝表示已处理),这一层没有别的孩子了,继续向上一层回溯。
- 17撤销 根·左,掩码翻回「根·左」这边走完了,回溯:把它从路径里去掉、数字 3 的奇偶翻回原样(标蓝表示已处理),回到父节点,继续走还没走的另一边。
- 18根·右 的值 1,翻其奇偶走到「根·右」(值 1,紫色)。把数字 1 的出现次数奇偶翻一下。它还有孩子,继续往下走。
- 19根·右·左 的值 2,翻其奇偶走到「根·右·左」(值 2,紫色)。把数字 2 的出现次数奇偶翻一下。它没有孩子,是叶子,马上判定这条路径。
- 20奇数个数 1 ≤ 1 → 伪回文到达叶子「根·右·左」。这条路径出现奇数次的数字只有 1 一个(≤1),✓ 是伪回文,该叶变绿,计数 +1 = 1。
- 21撤销 根·右·左,掩码翻回「根·右·左」这边走完了,回溯:把它从路径里去掉、数字 2 的奇偶翻回原样(标蓝表示已处理),回到父节点,继续走还没走的另一边。
- 22根·右·右 的值 1,翻其奇偶走到「根·右·右」(值 1,紫色)。把数字 1 的出现次数奇偶翻一下。它没有孩子,是叶子,马上判定这条路径。
- 23奇数个数 1 ≤ 1 → 伪回文到达叶子「根·右·右」。这条路径出现奇数次的数字只有 2 一个(≤1),✓ 是伪回文,该叶变绿,计数 +1 = 2。
- 24撤销 根·右·右,掩码翻回「根·右·右」这边走完了,回溯:把它从路径里去掉、数字 1 的奇偶翻回原样(标蓝表示已处理),这一层没有别的孩子了,继续向上一层回溯。
- 25撤销 根·右,掩码翻回「根·右」这边走完了,回溯:把它从路径里去掉、数字 1 的奇偶翻回原样(标蓝表示已处理),这一层没有别的孩子了,继续向上一层回溯。
- 26撤销 根,掩码翻回「根」这边走完了,回溯:把它从路径里去掉、数字 2 的奇偶翻回原样(标蓝表示已处理)。根节点退出,整棵树遍历结束,准备汇总答案。
- 27伪回文路径数 = 2全部路径走完,绿色的两片叶子(根·右·左、根·右·右)对应的路径是伪回文,答案 2。判定全靠「出现奇数次的数字 ≤ 1」。
⚠️ 容易写错的地方
✗ 错：真的去枚举排列判回文
✓ 对：只数各数字出现次数的奇偶
能重排成回文 ⟺ 奇数次的数字 ≤ 1,不必排列
✗ 错：允许「全是偶数」之外才算
✓ 对：0 个奇数(偶长)或 1 个奇数(奇长)都行
回文正中间可放唯一一个出现奇数次的数字
✗ 错：回溯忘了翻回掩码
✓ 对：离开节点要 mask ^= 1<<val 还原
不还原会污染兄弟分支的奇偶统计(用递归传参可天然避免)
完整代码（Python / C++ / Java）
Python
from typing import Optional
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(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)C++
#include <vector>
using namespace std;
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *l, TreeNode *r) : val(x), left(l), right(r) {} };
class Solution {
public:
int pseudoPalindromicPaths(TreeNode* root) { return dfs(root, 0); }
private:
int dfs(TreeNode* node, int mask) {
if (!node) return 0;
mask ^= 1 << node->val;
if (!node->left && !node->right) return (mask & (mask - 1)) == 0;
return dfs(node->left, mask) + dfs(node->right, mask);
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } }
class Solution {
public int pseudoPalindromicPaths(TreeNode root) { return dfs(root, 0); }
private int dfs(TreeNode node, int mask) {
if (node == null) return 0;
mask ^= 1 << node.val;
if (node.left == null && node.right == null) return (mask & (mask - 1)) == 0 ? 1 : 0;
return dfs(node.left, mask) + dfs(node.right, mask);
}
}复杂度
时间
O(n)
每个节点访问一次
空间
O(h)
递归栈深 = 树高 h;掩码 O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 二叉树中的伪回文路径 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用掩码而不用一个长度 10 的计数数组？+
我们只关心每个数字出现次数的「奇偶」,不关心具体次数。奇偶只有两态,用 1 个 bit 表示、9 个数字用 9 个 bit,异或天然完成翻转,判回文用一次 mask&(mask-1) 即可,比维护并扫描计数数组更省更快。计数数组也能做,只是更重。
回溯时这道题为什么可以「不显式还原」？+
因为 mask 是按值传参进递归的:每层 dfs 拿到的是「父亲传下来的 mask 副本」,自己异或后传给孩子,返回父亲时父亲的 mask 没变。所以用传参写法天然回溯;若改用共享的全局 mask,就必须在离开节点时手动异或还原。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 二叉树中的伪回文路径 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。