题目简介：
给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。
请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。
示例 1：
1
2
3
4
| 输入：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：
1
2
3
4
| 输入：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：
提示：
- 给定二叉树的节点数目在
1 到 10^5 之间。
- 节点值在
1 到 9 之间。
思路：
第一次在周赛里做出第三道题，还是有点开心的。
首先要做的就是将根节点到叶子结点的所有路径存下来，深度优先遍历即可，需要注意逻辑上的问题。在到达叶子结点时需保存完整的路径，在返回父节点时需删除当前结点。
将路径都找出来后，便是要验证是否存在回文串了，我这里用的方法应该不是最优法，不过暂时还想不到更好的方法。
首先将数组进行排序，然后进行遍历，若当前元素与下一个元素相等，则跳一个元素；若不等，则count++，即存在count个只出现了一次的元素。
然后根据路径长度的奇偶性来判定：
- 若路径长度为奇数，则最多可以允许一个
count；count == 0的情况，说明出现一次的元素在排序后的数组的最后面。
- 若路径长度为偶数，则不能有只存在一次的元素。
最后返回符合条件的路径数目即可。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
class Solution {
public:
vector<vector<int>> allPath;
void findAllPath(TreeNode*pRoot, vector<int>&path){
if (pRoot == NULL)
{
return;
}
path.push_back(pRoot-> val);
if (pRoot->left == NULL && pRoot->right == NULL)
{
allPath.push_back(path);
}
if (pRoot->left != NULL)
{
findAllPath(pRoot->left, path);
}
if (pRoot->right != NULL)
{
findAllPath(pRoot->right, path);
}
path.pop_back();
}
bool judge(vector<int> path){
int temp = 0;
int count = 0;
sort(path.begin(), path.end());
for(int i = 0; i < path.size() - 1; i++){
if(path[i] == path[i + 1]){
i++;
}else{
count++;
}
}
if(path.size() % 2 == 0 && count == 0)
return true;
if(path.size() % 2 != 0 && count <= 1)
return true;
return false;
}
int pseudoPalindromicPaths (TreeNode* root) {
vector<int> path;
findAllPath(root, path);
int num = 0;
for(int i = 0; i < allPath.size(); i++){
if(judge(allPath[i]))
num++;
}
return num;
}
};
|
