首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Python|Dfs回溯解二叉树伪回文

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

作者头像
算法与编程之美
发布2020-06-03 08:59:08
5190
发布2020-06-03 08:59:08
举报

问题描述

给你一棵二叉树,每个节点的值为 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 团队

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-05-31,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法与编程之美 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档