↓Skip to main content
  1. Posts/

LeetCode-1457 二叉树中的伪回文路径

·1 min·
Table of Contents

LeetCode-1457 二叉树中的伪回文路径 #

Solution 1 #

伪回文路径要求路径中出现次数为奇数次的数字至多为 1 个, 回溯计数即可.

代码如下:

class Solution:
    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
        ans = 0
        book = defaultdict(int)
        
        def f(node):
            if node is None:
                return 
            book[node.val] += 1
            if node.left is node.right and sum([1 if v & 1 else 0 for k, v in book.items()]) <= 1:
                nonlocal ans
                ans += 1
            else:
                f(node.left)
                f(node.right)
            book[node.val] -= 1
            
        f(root)
        return ans

Solution 2 #

用位运算优化. 代码如下:

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