Find Duplicate Subtrees - Leetcode 652 - Python
HTML-код
- Опубликовано: 12 июн 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/find-du...
0:00 - Read the problem
2:05 - Drawing Explanation
9:30 - Coding Explanation
leetcode 652
#neetcode #leetcode #python
I'll be traveling next week, so unfortunately I won't be able to do the daily problems for about 7 days. Will continue them as soon as I get back tho! 🚀
Enjoy your travels!!
this question can be done in O(n) time complexity
we are storing strings so it will take O(n2) time
One leetcode a day, keeps unemployment away. Thanks for the content.
your explanations keep getting better. thanks for the daily
dude is in another level
Thanks Neetcode, you earned me the February Badge for this month's Leetcode.
You have the best explanations on entire RUclips! Will miss you for next week :(
Thank you for starting this series!
Thanks for the mind blowing solution. For me the key observation was the fact that adding the null value while serializing the Tree makes the resultant string unique to the tree itself which generally is not the case with only preorder, postorder or inorder traversal.
Thanks, Neet for the clear solution, two major points here:
1. Time complexity, O(n^2), we need to visit each node, and the maximum length for hashing the string would be O(n) so overall is n * O(n);
2. The way this question asks has some issues, basically, we should only return sets of duplicate trees which does the map[key].size() == 1 come from. For eg, using the example in the video, node 4 itself is duplicated and should return {{2, 4}, {4}, {4}} if we don't add that check.
your videos literally have the best explanations. love your videos and keep on doing it. Have a great trip.
concept of serialising the tree into string and storing it to hash map is a real hack, keep up the good job
Very nice! I came up with the same idea but had some trouble implementing it
Thank you so much sir. Keep helping us by posting such content.
Awesome solution
So as we are doing serialization and storing it a hashmap, we are having O(n) time complexity for lookup. Correct me if I am wrong.
A small suggestion: you can put the difficulty of the problems on thumbnail!
Thanks for the content btw.
@neetcode Great explaination, I followed the same logic , but instead of adding the node to the defualt dict i just maintained the count, it ran a bit faster and saves huge memory. I directly saved the node to the res.
attaching my code:
class Solution:
def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
subtrees=defaultdict(int)
def serialize(root):
if root==None:
return 'N'
else:
res=str(root.val)+","+serialize(root.left)+","+serialize(root.right)
subtrees[res]+=1
if subtrees[res]==2:
ans.append(root)
return res
res=''
ans=[]
serialize(root)
return ans
why did you use if subtrees[res]==2 ? defaultdict(int) returns 0 as default value
i think it's because you have added subtrees[res]+=1 before if condition, if you write after if the condition becomes ==1
@@infernoo365 Yes, I felt it clear if I write it this way. that was a bit confusing.
Awesome ❤
This question is poorly described in leetcode. However, Neetcode explained it very well. Thank you!
Hi, I think "subtrees" could just be a `set` of strings (we do not need a key-value pair in this question).
Why do we need to return s from the dfs function? It's not working when I don't return it, but I can't see why it's important?
Nice problem
The Inorder traversal wont work for this example:
[0,0,0,0,null,null,0,null,null,null,0]
0
node1-> 0 0
0 0
Good comment bro, I got stuck on the same test case with in-order. Your comment helped me figure out the issue!
Same problem, I don't understand why though
I just had one small doubt.How are we really sure that the serialisation gives a unique subtree configuration.If the tree is not a BST, we need atleast one of preorder and postorder and an inorder to uniquely construct a tree.So just curious does this always work.And for inorder case, it might give 2 symmetric trees as equal even if they are not right?
Thats y he said we should add null values.
@@SarveshRansubhe Adding 'null' still fails with InOrder, post and preorder works. To see why InOrder fails, see Alone Beast's comments.
inorder failed at [0,0,0,0,null,null,0,null,null,null,0]. Only pre and post work.
I have a doubt? Why are we using strings. Would lists not work?
I have replaced string representation with hashes and I think I have reduced TC and SC to linear. Tell me what I am doing wrong?
Approach is to Use sha1 hash string representation to keep track of subtree. Since string representation can grow the size of tree, while sha1 hash string will be fixed length always.
from hashlib import sha1
class Solution:
def dfs(self, root) -> str:
if not root:
return "Null"
else:
left_hash = self.dfs(root.left)
right_hash = self.dfs(root.right)
res = left_hash + right_hash
res += str(root.val)
if res in self.hashes and res not in self.result_hashes:
self.result_hashes.add(res)
self.results.append(root)
else:
self.hashes.add(res)
return sha1(res.encode('utf-8')).hexdigest()
def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
self.hashes = set()
self.result_hashes = set()
self.results = []
self.dfs(root)
return self.results
Though it is explained here, I am still not sure why the runtime is O(n^2). The DFS is touching all nodes only once and the string is being generated one step at a time. Wha am I missing?
Dic needs to compute the hash for key which is not simple here
We need to get all nodes connected of this sub tree thats why we need n for hash
So all time n for hash times n for dfs
can anyone please explain me what line # 17 is doing ?
Using a tuple instead of a string is more efficient
Why hashing takes O(n) time complexity?
Did not work for [2,1,11,11,null,1]
works for me
i thinks this postorder traversal not preorder
Bad test cases one of the two others namely inorder or postorder also works and the other doesnt which is wrong both of inorder and postorder shouldnt work as only preorder can give a unique tree string representation google the proof.