【教3妹学编程-算法题】二叉树中的伪回文路径

3妹：好冷啊， 冻得瑟瑟发抖啦
2哥 : 又一波寒潮来袭， 外面风吹的呼呼的。
3妹：今天还有雨，2哥上班记得带伞。
2哥 : 好的
3妹：哼，不喜欢冬天，也不喜欢下雨天，要是我会咒语，一直停留在春天就好啦，四季如春。
2哥：想得美， 接受现实吧。说到咒语，我今天看到一个关于咒语的题目，你来做一下吧~
3妹：好的，我要上班去了，你发我微信上，我通勤路上看一下~

题目：

给你一棵二叉树，每个节点的值为 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 <= Node.val <= 9

思路：

枚举，
根据意义要求，给定数字 tagret，找到所有满足 j<i且 nums[i]+nums[j]<target，可以直接枚举所有的下标对 (i,j)，检测该下标对对应的元素之和是否满足小于等于 target 即可。
获得授权，非商业转载请注明出处。

java代码：

/*** Definition for a binary tree node.* public 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) {int[] counter = new int[10];return dfs(root, counter);}public int dfs(TreeNode root, int[] counter) {if (root == null) {return 0;}counter[root.val]++;int res = 0;if (root.left == null && root.right == null) {if (isPseudoPalindrome(counter)) {res = 1;}} else {res = dfs(root.left, counter) + dfs(root.right, counter);}counter[root.val]--;return res;}public boolean isPseudoPalindrome(int[] counter) {int odd = 0;for (int value : counter) {if (value % 2 == 1) {odd++;}}return odd <= 1;}
}