【Leetcode Daily】1457二叉树中的伪回文路径

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是从根节点到叶子节点的路径经过的数值，能否凑出回文序列。

思路分享

• 于灵神思路相似，都是通过数组记录已有数字的奇偶性，只要奇数的数字小于等于 1 即可（全偶数或者一个奇数都能组成回文序列）

• 但灵神思路更好的一点是，通过直接维护九个数字的奇偶性，就不用维护记录了几个数字。甚至后面通过位运算，将一个数字的奇偶性映射成对应位的 1 和 0. 而且 mask & (mask - 1) == 0 更是神来之笔，无论 mask 为 0 还是只有一个 1 ，都会满足这个式子，非常快得检测出来是否满足答案。

  https://leetcode.cn/problems/pseudo-palindromic-paths-in-a-binary-tree/solutions/2540903/yi-bu-bu-you-hua-cong-shu-zu-dao-wei-yun-hu0b/

代码解答（强烈建议自行解答后再看）

• 参考题解

# 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:
        rec = [0] * 9 
        ans = 0
        def dfs(root: Optional[TreeNode], odd = 0, even = 9):
            if not root:
                return 
            nonlocal rec
            if rec[root.val - 1] % 2 == 1:
                if rec[root.val - 1] > 0:
                    odd -= 1
                even += 1
            else:
                if rec[root.val - 1] > 0:
                    even -= 1
                odd += 1
                
            rec[root.val - 1] += 1
            
            if not root.left and not root.right:
                if odd <= 1:
                    # print(odd, even, rec)
                    nonlocal ans 
                    ans += 1
            else:
                dfs(root.left, odd, even)
                dfs(root.right, odd, even)
            rec[root.val - 1] -= 1
        dfs(root)
        return ans