1457. Pseudo-Palindromic Paths in a Binary Tree - Explanation

# 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:
        count = defaultdict(int)
        odd = 0

        def dfs(cur):
            nonlocal odd
            if not cur:
                return 0

            count[cur.val] += 1
            odd_change = 1 if count[cur.val] % 2 == 1 else -1
            odd += odd_change

            if not cur.left and not cur.right:
                res = 1 if odd <= 1 else 0
            else:
                res = dfs(cur.left) + dfs(cur.right)

            odd -= odd_change
            count[cur.val] -= 1
            return res

        return dfs(root)

# 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:
        count = [0] * 10
        odd = 0

        def dfs(cur):
            nonlocal odd
            if not cur:
                return 0

            count[cur.val] ^= 1
            odd += 1 if count[cur.val] else -1

            if not cur.left and not cur.right and odd <= 1:
                res = 1
            else:
                res = dfs(cur.left) + dfs(cur.right)

            odd -= 1 if count[cur.val] else -1
            count[cur.val] ^= 1

            return res

        return dfs(root)

# 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:
        def dfs(node, path):
            if not node:
                return 0

            path ^= 1 << node.val
            if not node.left and not node.right:
                return 1 if (path & (path - 1)) == 0 else 0

            return dfs(node.left, path) + dfs(node.right, path)

        return dfs(root, 0)

# 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:
        res = 0
        q = deque([(root, 0)])
        while q:
            node, path = q.popleft()
            path ^= 1 << node.val

            if not node.left and not node.right:
                if path & (path - 1) == 0:
                    res += 1
                continue

            if node.left:
                q.append((node.left, path))
            if node.right:
                q.append((node.right, path))

        return res

# 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:
        count = 0
        stack = [(root, 0)]
        while stack:
            node, path = stack.pop()
            path ^= (1 << node.val)

            if not node.left and not node.right:
                if path & (path - 1) == 0:
                    count += 1
            else:
                if node.right:
                    stack.append((node.right, path))
                if node.left:
                    stack.append((node.left, path))

        return count