二叉树中的伪回文路径
给你一棵二叉树，每个节点的值为 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^5之间。 - 节点值在
1到9之间。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1457
解题思路分析：
老规矩，二叉树应考虑使用dfs来解题。另外判断二叉树路径是否为伪回文路径的问题应该是在leetcode中首次出现（也许是我还没刷到过），这个问题难度并不大，我们只要统计出路径中每种字符出现的个数，然后在路径尾部来判断“落单”字符的个数，如果个数小于等于1代表该路径为伪回文路径，反之则不是。这里简单来解释一下，对于一个回文，就像洋葱一般，右外层到内层都是首尾相同的，因此每种出现过的字符数量一定是偶数个。只存在一个特例即是长度为奇数的回文正中间的那个字符，只有它存在单独出现的可能。
实现代码：
int res=0;
public int pseudoPalindromicPaths (TreeNode root) {
help(root,new int[10]);
return res;
}
void help(TreeNode root, int[] count){
count[root.val]++;
if(root.left!=null) help(root.left, count);
if(root.right!=null) help(root.right, count);
if(root.left==null&&root.right==null){
int c=0;
for(int i=1;i<=9;i++){
c+=(count[i]%2);
if(c>1) break;
}
if(c<=1) res++;
}
count[root.val]--;
}本题解法执行时间为4ms。
Runtime: 4 ms, faster than 97.33% of Java online submissions for Pseudo-Palindromic Paths in a Binary Tree.
Memory Usage: 57.4 MB, less than 100.00% of Java online submissions for Pseudo-Palindromic Paths in a Binary Tree.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1457-pseudo-palindromic-paths-in-a-binary-tree-解题思路分析/