二叉树中的伪回文路径（DFS+简单回溯）
问题：
思路：
若一条路径中有大于1个数出现了奇数次，则不能构成回文串
采用一个数组作为计数器，记录每个数出现的次数
构造函数check判断计数器中的记录是否能构成回文串
进行dfs遍历，当一个新节点放入栈顶（进入新的递归层），更新该节点值的计数器，若该节点为叶子节点，检查计数器，若满足条件，则满足条件路径数+1。之后对左右子树调用dfs函数，调用完成后该节点值在计数器中的数目-1（ 节点退栈，进行回溯 ）
代码：
/**
* 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:
int check( vector<int>& count )
{
int i;
int flag=0;
for( i=1;i<count.size();i++ )
{
if( count[i]%2==1 )
flag++;
}
if( flag<=1 )
return 1;
return 0;
}
void dfs( TreeNode* root,vector<int>& count,int& ans )
{
if( root==NULL )
return ;
count[ root->val ]++;
if( root->left==NULL && root->right==NULL )
{
ans+=check( count );
}
dfs( root->left,count,ans );
dfs( root->right,count,ans );
count[ root->val ]--;
}
int pseudoPalindromicPaths (TreeNode* root) {
vector<int> count( 10,0 );
int ans=0;
dfs( root,count,ans );
return ans;
}
};
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/153818.html
