Even better approach: - we don’t care about count, just the parity; so at the leaf we only need to check if at most 1 digit occurred an odd number of times on the path - to store parity we only need booleans, but even better - bits - so it’s enough to pass an int with parities (bits set for odd parities) of digits down the tree; when in leaf, check if number of set bits is
# 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 s = set() def dfs(r): nonlocal res if r.val in s: s.remove(r.val) else: s.add(r.val) if r.left is None and r.right is None: if len(s)
just to double check, on the line: res = dfs(curr.left) + dfs(curr.right) We keep doing recursive calls of dfs(curr.left) and only reach the dfs(curr.right) call once the left child is a leaf node despite both these dfs calls being written on the same line?
class Solution: def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int: c = [0] * 10 def dfs(node): if not node: return 0 c[node.val] += 1 if not node.left and not node.right: flag = 0 for i in range(10): if c[i] %2 != 0: flag += 1 c[node.val] -= 1 if flag
my solution to count at most one odd count: class Solution: def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int: freq = defaultdict(int) res = 0 def dfs(root): nonlocal res if not root: return freq[root.val] += 1 if root.left is None and root.right is None: odd = sum(1 for v in freq.values() if v % 2 != 0) if odd
I solved it using this approach and I think is very cool but I saw that is possible using XOR and I don't have very clear how to solve it using XOR I know that using XOR I can eliminate duplicates like 2^2 = 0 but I am not sure how to handle when is odd like [2,2,1]
Odd occuring values will not be removed ,then in final we check how many odds we have if less than 2 we are ok. X&(x-1) ==0 checks if only 1 bit is set to 1 in x
BFS Solution. Looks more clean? class Solution: def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int: root_arr=[0]*9 q=deque([[root,root_arr]]) res=0 while q: cur,arr=q.popleft() new_arr=arr.copy() new_arr[cur.val-1]+=1 if not cur.right and not cur.left: n_odd=sum([1 if x%2 else 0 for x in new_arr]) if n_odd
If every digit occurs an even number of times, then we can rearrange it into a palindrome trivially. Try that on your own. 224466 -> 246642 That is the case of the even length palindrome Anything of odd length is an even number + an odd number The odd case palindrome exists when the odd section is in the middle of the palindrome. I will put the odd section in brackets for you. 122 -> 212 abbbb -> bb[a]bb aaabbbb -> bb[aaa]bb Does it help?
Wow, a 13-minute clip. A defaultdict for keys from 1 to 9. 13 lines of function body where 4 would be more than enough. An integer counter where 1 bit is enough. Is all that wandering in the dark really necessary?
Even better approach:
- we don’t care about count, just the parity; so at the leaf we only need to check if at most 1 digit occurred an odd number of times on the path
- to store parity we only need booleans, but even better - bits
- so it’s enough to pass an int with parities (bits set for odd parities) of digits down the tree; when in leaf, check if number of set bits is
I solved it in a similar way but I used a set() and if the node.val is already in the set I just removed it and then checked if the len(set)
# 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
s = set()
def dfs(r):
nonlocal res
if r.val in s:
s.remove(r.val)
else:
s.add(r.val)
if r.left is None and r.right is None:
if len(s)
class Solution:
def pseudoPalindromicPaths(self, root: Optional[TreeNode]) -> int:
# def pali(path: dict) -> bool:
# one_odd = False
# count1=0
# for count in path.values():
# if count % 2 == 1:
# count1+=1
# return count1==1 or count1==0
def pali(path: dict) -> bool:
one_odd = False
for count in path.values():
if count % 2 == 1:
if one_odd:
return False
one_odd = True
return True
def dfs(root, path):
if not root:
return 0
path[root.val] += 1
count = 0
if not root.left and not root.right:
count = 1 if pali(path) else 0
else:
count = dfs(root.left, path) + dfs(root.right, path)
path[root.val] -= 1 # Backtrack
return count
return dfs(root, defaultdict(int))
Backtrack this was more intutive for me
just to double check, on the line:
res = dfs(curr.left) + dfs(curr.right)
We keep doing recursive calls of dfs(curr.left) and only reach the dfs(curr.right) call once the left child is a leaf node despite both these dfs calls being written on the same line?
Yeah that's right
class Solution:
def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
c = [0] * 10
def dfs(node):
if not node:
return 0
c[node.val] += 1
if not node.left and not node.right:
flag = 0
for i in range(10):
if c[i] %2 != 0:
flag += 1
c[node.val] -= 1
if flag
my solution to count at most one odd count:
class Solution:
def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
freq = defaultdict(int)
res = 0
def dfs(root):
nonlocal res
if not root:
return
freq[root.val] += 1
if root.left is None and root.right is None:
odd = sum(1 for v in freq.values() if v % 2 != 0)
if odd
The description made me think we were looking for all paths.
Would you consider this solution backtracking as well as a depth first search?
Backtracking I would say
What happened to the fantastic dict.get(key, 0) ?!!?!
I solved it using this approach and I think is very cool but I saw that is possible using XOR and I don't have very clear how to solve it using XOR I know that using XOR I can eliminate duplicates like 2^2 = 0 but I am not sure how to handle when is odd like [2,2,1]
Odd occuring values will not be removed ,then in final we check how many odds we have if less than 2 we are ok.
X&(x-1) ==0 checks if only 1 bit is set to 1 in x
Great explanation as always . Thank you.
Is this inorder? Wouldn't it be preorder traversal?
Yeah thats right, it's technically preorder
Can you add Java for data structure
BFS Solution. Looks more clean?
class Solution:
def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
root_arr=[0]*9
q=deque([[root,root_arr]])
res=0
while q:
cur,arr=q.popleft()
new_arr=arr.copy()
new_arr[cur.val-1]+=1
if not cur.right and not cur.left:
n_odd=sum([1 if x%2 else 0 for x in new_arr])
if n_odd
Nice!
Thank you so much
too tough to grasp the concept!
If every digit occurs an even number of times, then we can rearrange it into a palindrome trivially. Try that on your own.
224466 -> 246642
That is the case of the even length palindrome
Anything of odd length is an even number + an odd number
The odd case palindrome exists when the odd section is in the middle of the palindrome. I will put the odd section in brackets for you.
122 -> 212
abbbb -> bb[a]bb
aaabbbb -> bb[aaa]bb
Does it help?
I first came up with the naive all permutations solutions but it's always a hasmap dammit
Also, I always forget about collections, so I'd do count = {n:0 for n in range(1,10)} for the hash
Wow, a 13-minute clip.
A defaultdict for keys from 1 to 9.
13 lines of function body where 4 would be more than enough.
An integer counter where 1 bit is enough.
Is all that wandering in the dark really necessary?
Not so good this time