日拱一卒（18）——leetcode学习记录：二叉树中的伪回文路径
一、题目
给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。
请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。
二、思路
-
理解伪回文路径的概念：
- 首先，我们要明白什么是伪回文路径。对于一条从根节点到叶节点的路径，这条路径上的节点值组成一个序列。如果这个序列可以通过重新排列，变成一个回文序列，那么这条路径就是伪回文路径。
- 回文序列就是正读和反读都一样的序列，比如 "aba" 或 "aabb"。对于我们的问题，节点值范围是 1 到 9，所以我们只需要关注这些数字出现的次数。
- 对于一个序列要成为伪回文序列，其中最多只能有一个数字出现的次数是奇数，其他数字出现的次数都必须是偶数。例如，对于序列 "121"，数字 1 出现两次（偶数次），数字 2 出现一次（奇数次），可以重新排列成 "112" 形成回文，所以是伪回文序列；对于序列 "123"，三个数字都只出现一次，不满足最多一个数字出现奇数次，所以不是伪回文序列。
-
使用深度优先搜索（DFS）遍历二叉树：
- 我们要遍历二叉树从根节点到所有叶节点的路径。这就像走迷宫一样，从起点（根节点）出发，每次选择一个分支（左子节点或右子节点）走，直到走到终点（叶节点）。
- 在走的过程中，我们要记录下经过的节点值。
- 当到达叶节点时，检查这条路径是否是伪回文路径。
-
记录节点值的出现次数：
- 我们可以使用一个列表（或数组）来记录每个数字（1 到 9）出现的次数。开始时，列表中所有数字的计数都是 0。
- 当我们经过一个节点时，就把该节点值对应的计数加 1。
- 当我们回溯（从叶节点往回走）时，要把这个计数减 1，因为我们要检查其他可能的路径。
-
检查是否是伪回文路径：
- 当到达叶节点时，我们检查记录节点值出现次数的列表。
- 计算列表中出现奇数次的数字的数量。如果这个数量小于等于 1，那么这条路径就是伪回文路径。
具体步骤：
-
开始 DFS 遍历：
- 从根节点开始，将根节点的值对应的计数加 1。
- 然后递归地对左子节点和右子节点进行 DFS 遍历。
- 每次递归调用时，会重复上述加计数的操作。
-
到达叶节点：
- 当到达叶节点时，检查列表中出现奇数次的数字的数量。
- 如果这个数量小于等于 1，说明这条路径是伪回文路径，我们可以将结果加 1。
-
回溯操作：
- 在从叶节点往回走时，要把当前节点值对应的计数减 1，这样可以继续检查其他可能的路径。
三、题解
# 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:
def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
mylist = [0]*10
return self.dfs(mylist,root)
# 递归
def dfs(self,mylist,root):
ans = 0
# 初始条件
if not root:
return 0
mylist[root.val] += 1
if not root.left and not root.right:
ans = int(self.isPalindromic(mylist))
else:
ans = self.dfs(mylist,root.left) + self.dfs(mylist,root.right)
mylist[root.val] -= 1
return ans
def isPalindromic(self,mylist):
odd = 0
for value in mylist:
if value%2 == 1:
odd += 1
return odd <= 1