LeetCode contest 190 5418. 二叉树中的伪回文路径 Pseudo-Palindromic Paths in a Binary Tree

简介: LeetCode contest 190 5418. 二叉树中的伪回文路径 Pseudo-Palindromic Paths in a Binary Tree

LeetCode contest 190 5418. 二叉树中的伪回文路径 Pseudo-Palindromic Paths in a Binary Tree


Table of Contents

一、中文版

二、英文版

三、My answer

四、解题报告


一、中文版

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

相关文章
|
2月前
【LeetCode 35】112.路径总和
【LeetCode 35】112.路径总和
28 0
|
2月前
【LeetCode 36】113.路径总和II
【LeetCode 36】113.路径总和II
31 0
|
2月前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
26 2
|
2月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
21 0
|
2月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
15 0
|
2月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
23 0
|
2月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
22 0
|
2月前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
19 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
128 2