[leetcode] 1457. Pseudo-Palindromic Paths in a Binary Tree

[leetcode] 1457. Pseudo-Palindromic Paths in a Binary Tree

Description

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.

分析

题目的意思是：判断二叉树从根结点到叶子结点的数能否构成回文子串。找出能构成回文子串的个数，我的思路也很直接，从根结点遍历到叶子结点之后，然后判断一下是否是回文子串就行了。

代码

# 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 = rightclass Solution: def solve(self,root,ans): if(root is None): return ans.append(root.val) if(root.left is None and root.right is None): self.res+=self.isPalindrome(ans) self.solve(root.left,ans) self.solve(root.right,ans) ans.pop(-1) def isPalindrome(self,ans): counter=collections.Counter(ans) cnt=0 for k,v in counter.most_common(): if(v%2==1): cnt+=1 if(cnt>1): return 0 return 1 def pseudoPalindromicPaths (self, root: TreeNode) -> int: self.res=0 self.solve(root,[]) return self.res

参考文献

​​[LeetCode] [Java/C++/Python] At most one odd occurrence​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。