问题描述
给你一棵二叉树，每个节点的值为 1 到 9 。称二叉树中的一条路径是 「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。
请你返回从根到叶子节点的所有路径中伪回文路径的数。
示列1：
class TreeNode: def init(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def pseudoPalindromicPaths (self, root: TreeNode): self.ass=[0,0,0,0,0,0,0,0,0,0] #计数路径中数字的个数 self.res=0 #记录符合路径的个数 self.dfs(root,[]) #深搜回溯 return self.res def dfs(self,root,path): #回溯方法 if root is None: return self.ass[root.val]+=1 #将节点数值对应的数字个数加1 if root.left is None and root.right is None:#当达到叶子节点时开始判断是否为伪回文 x=0 for i in range(10): if self.ass[i]%2!=0 and self.ass[i]!=0:#记录数字个数为奇数的数目 x+=1 if x<2: self.res+=1#如果路径中数字个数为奇数的数目为1或0，就是伪回文 if root.left: self.dfs(root.left,path) if root.right: self.dfs(root.right,path) self.ass[root.val]-=1 |
|---|
结语
这道题就是二叉树的遍历和伪回文的判断，树的遍历基本上是用dfs来遍历的，所以遇到二叉树就要想到dfs或者bfs来遍历，还有就是回溯的点，这道题很简单，回溯的点就是叶子节点的时候就可以回溯了。