Python|Dfs回溯解二叉树伪回文

欢迎点击「算法与编程之美」↑关注我们!

本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。

欢迎加入团队圈子!与作者面对面!直接点击!

问题描述

给你一棵二叉树,每个节点的值为 1 9 。称二叉树中的一条路径是 「伪回文」的,当它满足:路径经过的所有节点值的排列中,存在一个回文序列。

请你返回从根到叶子节点的所有路径中伪回文路径的数。

示列 1

图示 1.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]

解决方案

一开始的思路是遍历二叉树,记录每个叶子节点的路径,再求是否是伪回文。

判断伪回文的方法很简单,伪回文只需要满足一个条件,就是路径中最多只能有一个数是一个的,其他的都是两个,比如 [1,1,1,1,1,2] 1 5 个是奇数, 2 1 个事奇数,所以不是伪回文, [1,1,1,1,2,2]1 4 个事偶数, 2 有两个是偶数,所以是伪回文。最后因为先把路径求出来再判断有点浪费时间复杂度。所以可以在遍历时就记录数字的奇数个数就好。

python 代码 :               

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 来遍历,还有就是回溯的点,这道题很简单,回溯的点就是叶子节点的时候就可以回溯了。

END

编  辑   |   王楠岚

责  编   |   王自强

where2go 团队

   

微信号:算法与编程之美          

长按识别二维码关注我们!

温馨提示: 点击页面右下角 “写留言”发表评论,期待您的参与!期待您的转发!

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章