Rest your mind for the rest of the day, then come back tomorrow and re-watch/re-code, for me that always makes something click if I didn't understand it fully before.
@@NeetCodeIO Thank you for the clarification ! I felt you only used it to clarify and share more about the thinking process but it was not necessary for the answer. Thanks again for everything you do. Really life saver!
oh i got the first and second max height of all the nodes and stored them in list, i knew that diameter can be in either three or both tree but i was not not able to guess which node should i take to connect bothe trees… so i again do a dfs to reroot tree on all nodes and got the minimum height of tree of all possible trees and joined them. The solution was linear time so it passed, but it gave me a headache to implement
We divide it by 2 to get the minimum path. For example: Let's say we have the maximum diameter from Tree1 as (1->2->3->4->5) and from Tree2 as (6->7->8->9->10). If we join Node (5) with Node (10) the diameter for the merged Tree will eventually increase (1->2->3->4->5->6->7->8->9->10), but we want to decrease it and get the minimum diameter of the merged tree. But if we divide the max diameter from both the trees by 2 and then try to merge it, we will get the minimum path. Take Node (3) from Tree1 and Node (8) from Tree2, the maximum diameter path for the merged Tree then will become (1->2->3->8->9->10) which will be the minimum diameter possible. That's why divide the max diameters by 2 and then +1 for adding the connection edge.
Can someone explain to me why the final answer is like the max(d1,d2,1+ceil(d1/2)+ceil(d2/2))? I understand the 3rd term where we are trying to minimize the diameter after merging the two trees as asked in the problem and also explained in the video, but why exactly are we also considering d1 and d2 individually? I did not understand it.
I found the minimum diameter after merging the tree (without the simple formula, just manually going through all nodes and finding the minimum longest path from any node in a tree and adding them for both trees) but forgot to also consider that a larger tree can still contain the diameter by itself.
Meh, I came here because I didn't want to code up my solution, since it seems tiresome, so I hoped to find a simpler one. But you got the exact same one lol
but how can we guarantee that 0 is always the root of the tree, leetcode did not mention in the problem statement, if 0 is not the root, how can we compare the children for max diameter?
It also updates the max_d for all children calls right? So that accounts for paths not going through 0. Suppose there is a diameter not going through 0: Some node on that diameter will be the child for which the function is called; then for the max paths for that child, the two branches that form the diameter will remain in the heap of that function call, thus creating the max_d for that function call which is then propagated upwards in the return values.
There is no root, but 0 is always the lowest index, hence if it's not empty you can choose it. If they aren't explicitly ordered, you just take any entry from the edges array.
For those of us who are still here trying to solve a problem like this during this time of the year, kudos to you! Kudos to NeetCode too~
Don't waste too much time on this problem, just watch the solution and learn :D
Thank you neetcode you changed my life for the better. Thank you leetcode for the wonderful xmas gift.
ur the best, happy christmas n happy new year buddy
Thank you and Happy New Year!
I have watched it like 4 times already and still can't wrap my head around the whole problem 😢
Rest your mind for the rest of the day, then come back tomorrow and re-watch/re-code, for me that always makes something click if I didn't understand it fully before.
have you solved the LC easy he mentioned?
yep i had to rewatch how to calculate the diameter of a binary tree, completely had forgotten about it.
I had to do, Tree Diameter, bfs + dfs solution and deep understand it
I am glad and sooo proud of myself that i came up with the same solution like you and i was able to code it up!! Practice really pays off
how long have you been solving problems on leetcode?
@@JamesBond-mq7pdbit more than a year, in that time i solved 650 problems and you?
@@KrystianRatajczyk-ko5rb more than a year and solved 370 problems. Still can't solve hard problems
Great explanation, as always. Thank you!
thank you for all what you are doing, you are the best leetcode teacher on youtube.
Very good explanation, thank you neetcode!!!
Merry Christmas!!
Can you redo the reconstruct itinerary problem and go over the Hierholzer's algorithm for eulerian paths
why did we define n and m if we never used them though ?
Good question honestly, I guess since we used a defaultdict it wasn't necessary to get n and m
@@NeetCodeIO Thank you for the clarification ! I felt you only used it to clarify and share more about the thinking process but it was not necessary for the answer.
Thanks again for everything you do. Really life saver!
oh i got the first and second max height of all the nodes and stored them in list, i knew that diameter can be in either three or both tree but i was not not able to guess which node should i take to connect bothe trees… so i again do a dfs to reroot tree on all nodes and got the minimum height of tree of all possible trees and joined them. The solution was linear time so it passed, but it gave me a headache to implement
but your solution was amazing and easy
This Christmas eve daily challenge is diabolical
Python heap is a min heap though. How could it be storing max values?
i was able to think of this approach but could not code it
Help me understand why we divide by 2? That’s the only part not making sense imo
We divide it by 2 to get the minimum path.
For example: Let's say we have the maximum diameter from Tree1 as (1->2->3->4->5) and from Tree2 as (6->7->8->9->10). If we join Node (5) with Node (10) the diameter for the merged Tree will eventually increase (1->2->3->4->5->6->7->8->9->10), but we want to decrease it and get the minimum diameter of the merged tree. But if we divide the max diameter from both the trees by 2 and then try to merge it, we will get the minimum path. Take Node (3) from Tree1 and Node (8) from Tree2, the maximum diameter path for the merged Tree then will become (1->2->3->8->9->10) which will be the minimum diameter possible. That's why divide the max diameters by 2 and then +1 for adding the connection edge.
solved it within 20min, all it takes is the observation, the actual solution is straightforward to be honest.
I don't know python how to find solutions in java
Can someone explain to me why the final answer is like the max(d1,d2,1+ceil(d1/2)+ceil(d2/2))? I understand the 3rd term where we are trying to minimize the diameter after merging the two trees as asked in the problem and also explained in the video, but why exactly are we also considering d1 and d2 individually? I did not understand it.
Lets say first graph has d1 = 10, secnd one has just 2. 3rd arg will give 7, but the diameter will still be 10.
You are talking to the real goat.
I found the minimum diameter after merging the tree (without the simple formula, just manually going through all nodes and finding the minimum longest path from any node in a tree and adding them for both trees) but forgot to also consider that a larger tree can still contain the diameter by itself.
Meh, I came here because I didn't want to code up my solution, since it seems tiresome, so I hoped to find a simpler one. But you got the exact same one lol
Okay, a little different. I wasn't going to use a heap, but a 2-tuple with the two max values. Close enough.
wait, I'm first?
Why the hell this is not on top today.......
Watched many other and just wasted time.
but how can we guarantee that 0 is always the root of the tree, leetcode did not mention in the problem statement, if 0 is not the root, how can we compare the children for max diameter?
It also updates the max_d for all children calls right? So that accounts for paths not going through 0. Suppose there is a diameter not going through 0: Some node on that diameter will be the child for which the function is called; then for the max paths for that child, the two branches that form the diameter will remain in the heap of that function call, thus creating the max_d for that function call which is then propagated upwards in the return values.
There is no root, but 0 is always the lowest index, hence if it's not empty you can choose it. If they aren't explicitly ordered, you just take any entry from the edges array.
It feels good when you can solve hard question in 15 minute without extra help
cool
congrats, this is a really hard one