1457.二叉树中的伪回文路径

链接：1457.二叉树中的伪回文路径
难度：Medium
标签：位运算、树、深度优先搜索、广度优先搜索、二叉树
简介：给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。

题解 1 - python

• 编辑时间：2023-11-25
• 执行用时：656ms
• 内存消耗：90.31MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode], val: int) -> int:
            if not node: return 0
            val ^= (1 << node.val)
            if not node.left and not node.right: return int(val == 0 or (val & (-val)) == val)
            return dfs(node.left, val) + dfs(node.right, val)
        return dfs(root, 0)