日拱一卒（18）——leetcode学习记录：二叉树中的伪回文路径

一、题目

给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。

请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。

二、思路

1. 理解伪回文路径的概念：

   • 首先，我们要明白什么是伪回文路径。对于一条从根节点到叶节点的路径，这条路径上的节点值组成一个序列。如果这个序列可以通过重新排列，变成一个回文序列，那么这条路径就是伪回文路径。
   • 回文序列就是正读和反读都一样的序列，比如 "aba" 或 "aabb"。对于我们的问题，节点值范围是 1 到 9，所以我们只需要关注这些数字出现的次数。
   • 对于一个序列要成为伪回文序列，其中最多只能有一个数字出现的次数是奇数，其他数字出现的次数都必须是偶数。例如，对于序列 "121"，数字 1 出现两次（偶数次），数字 2 出现一次（奇数次），可以重新排列成 "112" 形成回文，所以是伪回文序列；对于序列 "123"，三个数字都只出现一次，不满足最多一个数字出现奇数次，所以不是伪回文序列。

2. 使用深度优先搜索（DFS）遍历二叉树：

   • 我们要遍历二叉树从根节点到所有叶节点的路径。这就像走迷宫一样，从起点（根节点）出发，每次选择一个分支（左子节点或右子节点）走，直到走到终点（叶节点）。
   • 在走的过程中，我们要记录下经过的节点值。
   • 当到达叶节点时，检查这条路径是否是伪回文路径。

3. 记录节点值的出现次数：

   • 我们可以使用一个列表（或数组）来记录每个数字（1 到 9）出现的次数。开始时，列表中所有数字的计数都是 0。
   • 当我们经过一个节点时，就把该节点值对应的计数加 1。
   • 当我们回溯（从叶节点往回走）时，要把这个计数减 1，因为我们要检查其他可能的路径。

4. 检查是否是伪回文路径：

   • 当到达叶节点时，我们检查记录节点值出现次数的列表。
   • 计算列表中出现奇数次的数字的数量。如果这个数量小于等于 1，那么这条路径就是伪回文路径。

具体步骤：

1. 开始 DFS 遍历：

   • 从根节点开始，将根节点的值对应的计数加 1。
   • 然后递归地对左子节点和右子节点进行 DFS 遍历。
   • 每次递归调用时，会重复上述加计数的操作。

2. 到达叶节点：

   • 当到达叶节点时，检查列表中出现奇数次的数字的数量。
   • 如果这个数量小于等于 1，说明这条路径是伪回文路径，我们可以将结果加 1。

3. 回溯操作：

   • 在从叶节点往回走时，要把当前节点值对应的计数减 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