1 题目描述
题目链接：二叉树中的伪回文路径
2 解答思路
第一步：挖掘出相同的子问题 （关系到具体函数头的设计）
第二步：只关心具体子问题做了什么 （关系到具体函数体怎么写，是一个宏观的过程）
第三步：找到递归的出口，防止死递归 （关系到如何跳出递归）
2.1 相同的子问题（函数头设计）
计算二叉树中的伪回文路径，就是计算从根到叶子节点的每条路径是否是伪回文路径，最终返回伪回文路径的数量。
这里可以有两种理解：
第一种：计算左子树的伪回文路径数量 加上 右子树的伪回文路径
数量。
第二种：计算左子树的伪回文路径数量 和 右子树的伪回文路径，用全局变量记录。
如何判断是不是伪回文路径？
因为序列是打乱的，而且题目说每个节点的值是1到9。因此可以用一个大小为10的vector记录每个节点的数量。节点的值1对应下标1.节点的值2对应下标2… vector的值对应的是这个节点的值出现的次数。
最后统计每个值出现的次数：
如果是偶数回文，那么每个数应该都出现偶数次，对应的出现奇数次的数量为0
如果是奇数回文，那么出现奇数次的数量为1
因此，只需要判断最后出现的奇数次的数量是否小于等于1，如果是，则是伪回文路径。
类似哈希。
下面是示例：
这里只讲解第二种思路，根据第二种思路，函数头的设计如下：
void dfs(TreeNode* root, vector<int> count)
{
}
2.2 具体的子问题做了什么（函数体的实现）
根据之前的分析，具体的子问题做的事情：
1.判断是否是空节点，是就退出（也是递归的出口）
2.如果是叶子节点，判断是不是伪回文路径，是就res += 1
3.如果不是叶子节点，就继续计算该二叉树的左子树是否是伪回文路径 和 该二叉树的右子树是否是伪回文路径
3 总结
class Solution {
public:int res = 0;int pseudoPalindromicPaths(TreeNode* root) {vector<int> count(10, 0); // 数字范围是 1 到 9dfs(root, count);return res;}void dfs(TreeNode* root, vector<int> count) {if (root == nullptr)return;// 增加当前节点的值count[root->val]++;// 到达叶子节点时，检查伪回文条件if (root->left == nullptr && root->right == nullptr) {int oddCount = 0; // 记录出现奇数次数的数字个数for (int i = 1; i <= 9; ++i) {if (count[i] % 2 == 1) {oddCount++;}}// 只有一个或零个奇数的个数才算伪回文if (oddCount <= 1) {res++;}}// 递归调用左右子树dfs(root->left, count);dfs(root->right, count);}
};
