Keshawn_lu's Blog

Leetcode 5418. 二叉树中的伪回文路径

字数统计: 916阅读时长: 3 min
2020/05/24 Share

题目简介:

给你一棵二叉树,每个节点的值为 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
2
输入:root = [9]
输出:1

提示:

  • 给定二叉树的节点数目在 110^5 之间。
  • 节点值在 19 之间。

思路:

第一次在周赛里做出第三道题,还是有点开心的。

首先要做的就是将根节点到叶子结点的所有路径存下来,深度优先遍历即可,需要注意逻辑上的问题。在到达叶子结点时需保存完整的路径,在返回父节点时需删除当前结点。

将路径都找出来后,便是要验证是否存在回文串了,我这里用的方法应该不是最优法,不过暂时还想不到更好的方法。

首先将数组进行排序,然后进行遍历,若当前元素与下一个元素相等,则跳一个元素;若不等,则count++,即存在count个只出现了一次的元素。

然后根据路径长度的奇偶性来判定:

  • 若路径长度为奇数,则最多可以允许一个countcount == 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
/**
* Definition for a binary tree node.
* 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 *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
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;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: