Devin's Blog

Pseudo Palindromic Paths In A Binary Tree

3 min read

Intuition

  • A subproblem of this problem is Sum Root to Leaf Numbers.
  • For each path we find, we check if its a pseudo palindrome.
  • Instead of computing each permutation of the resultant note values, note that something is considered a pseudo palindrome if:
    • The count of values are even, and each value occurs an even amount of times
      • ex) aabb
    • The count of values are odd, and each value occurs an even amount of times except for one value which appears once an odd amount of times.
      • ex) abbba
  • We use a counter to keep track of the count of each of the values on that path, making sure to remove from its count after that node’s subroutine has finished (it has no left or right nodes left to process).

Complexity

Runtime

Space

for the counter, in which a counter could hold information on all the nodes in the case of nodes which go in a left or right chain.

Code

Cached

# 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:
        counter = Counter()
 
        @cache
        def r(node, path):
            if not node:
                return False
            
            count = 0
            counter[node.val] += 1
 
            if node.left or node.right:
                count = r(node.left, path + 1) + r(node.right, path + 1)
            else:
                # Count of odd values on that path
                odd_count = sum(val % 2 != 0 for val in counter.values())
 
                if (path % 2 == 0 and odd_count == 0) \
                    or (path % 2 == 1 and odd_count == 1):
                    count = 1
                        
            counter[node.val] -= 1
            return count
 
        return r(root, 1)

Nonlocal Counter

# 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:
        counter = Counter()
        res = 0
        def r(node, path):
            nonlocal res
            
            if not node:
                return
            
            counter[node.val] += 1
 
            if not (node.left or node.right):
                # If no values are odd on that path
                odd_count = sum(val % 2 != 0 for val in counter.values())
 
                # TODO Combine these
                if path % 2 == 0 and odd_count == 0:
                    res += 1
                elif path % 2 == 1 and odd_count == 1:
                    res += 1
                    
            r(node.left, path + 1)
            r(node.right, path + 1)
 
            counter[node.val] -= 1
 
        r(root, 1)
        return res

Cards

START Basic Front: Pseudo Palindromic Paths In A Binary Tree Back: Check whether values of a path occur an even amount of times, or with one element an odd number of times if there are an odd number of elements.

END

References

Graph View