LeetCode contest 190 5418. 二叉树中的伪回文路径 Pseudo-Palindromic Paths in a Binary Tree
Table of Contents
一、中文版
给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。
请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。
示例 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] 。
示例 2：
输入：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：
输入：root = [9] 输出：1
提示：
给定二叉树的节点数目在 1 到 10^5 之间。
节点值在 1 到 9 之间。
二、英文版
Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.
Return the number of pseudo-palindromic paths going from the root node to leaf nodes.
Example 1:
Input: root = [2,3,1,3,1,null,1] Output: 2 Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).
Example 2:
Input: root = [2,1,1,1,3,null,null,null,null,null,1] Output: 1 Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome).
Example 3:
Input: root = [9] Output: 1
Constraints:
The given binary tree will have between 1 and 10^5 nodes.
Node values are digits from 1 to 9.
三、My answer
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: # 判断是否为回文串，回文串的条件：有 0 个或 1 个字母出现奇数个 def judgeFakePa(self, counter): odd = 0 for x in counter: if x % 2 == 1: odd += 1 if odd <=1: self.ret += 1 # DFS 深搜 def dfs(self, root, counter: List): if not root: return counter[root.val] += 1 if not root.left and not root.right: self.judgeFakePa(counter) if root.left: self.dfs(root.left, counter) if root.right: self.dfs(root.right, counter) counter[root.val] -= 1 # 回溯 def pseudoPalindromicPaths (self, root: TreeNode) -> int: self.ret = 0 self.dfs(root, [0 for _ in range(10)]) return self.ret
四、解题报告
数据结构：树
算法：DFS
实现：拆分功能，分别实现判断回文串和 DFS。
1、回文串的条件：有 0 个或 1 个字母出现奇数个
2、深搜。参数 counter 是一个 list，下标 1-9 表示树节点的值（1-9），counter[1] 表示数值 1 出现的个数。
注意要有回溯，比如一个树是 [1,2,3]，那么它有两条路径：[1,2] 和 [1,3]，所以要先去掉 2 再加上 3。
![[leetcode~dfs]1261. 在受污染的二叉树中查找元素](https://ucc.alicdn.com/pic/developer-ecology/okfcmqqjwxoec_335a965e888346009ec98ec28a431196.png?x-oss-process=image/resize,h_160,m_lfit)