Pseudo-Palindromic Paths in a Binary Tree - Leetcode 1457 - Python
Vložit
- čas přidán 27. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/pseudo-...
0:00 - Read the problem
0:33 - Drawing Explanation
5:14 - Coding Explanation
leetcode 1457
#neetcode #leetcode #python
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)
Great explanation as always . Thank you.
what tool do you use to create video? especially the diagrams that you draw?
do you use a mouse or touch screen? I can never draw such neat circles using a mouse
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
Thank you so much
What happened to the fantastic dict.get(key, 0) ?!!?!
The description made me think we were looking for all paths.
Can you add Java for data structure
Would you consider this solution backtracking as well as a depth first search?
Backtracking I would say
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
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
Is this inorder? Wouldn't it be preorder traversal?
Yeah thats right, it's technically preorder
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
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
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
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?
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!
Not so good this time
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?