思路參考->https://leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree/solutions/2573237/leetcode-the-hard-way-explained-line-by-line/?envType=daily-question&envId=2024-01-24
1 #1457
2 #Runtime: 911 ms (Beats 96.43%)
3 #Memory: 136.7 MB (Beats 10.71%)
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 def pseudoPalindromicPaths (self, root, cnt = 0):
13 """
14 :type root: TreeNode
15 :rtype: int
16 """
17 if not root:
18 return 0
19 cnt ^= 1 << (root.val - 1)
20 if root.left is None and root.right is None:
21 return 1 if cnt & (cnt - 1) == 0 else 0
22 return self.pseudoPalindromicPaths(root.left, cnt) + self.pseudoPalindromicPaths(root.right, cnt)
23