your way of solving problem especially building from scratch and your explanation is very clear and good .please do more videos on most solved leetcode problems.
I just want to add a comment for people who might not understand thoroughly. We are not simply skipping child nodes and reaching grandchild nodes. The max() here means we are carried over the largest value of the subtree with the grandchild node as the root for each grant child root. That is amazing. Thank a ton
If dfs results on nodes could be cached, the solution would be more straightforward. Instead of using cache, dfs results are broken down to avoid repeated dfs on children nodes. A smart workaround but it takes some time to figure out.
I feel that this problem requires the combination of Dynamic Programming and DFS (Recursion), and you explained this problem very clearly. Even though I am using Java and you are using Python, I followed your logic and did this problem correctly. Thank you very much for your fantastic teaching and explanation!
Great Explaination. Loved it. Have been watching your videos for the past 2 months. This explaination forced me to do away with my laziness and comment.
I did it using bfs, borrowing from the solution to House Robber II from collections import deque class Solution: def rob(self, root) -> int: def bfs(): rob1, rob2 = 0, 0 queue = deque() queue.append(root) while queue: n = 0 for i in range(len(queue)): # level order node = queue.popleft() n += node.val if node.left: queue.append(node.left) if node.right: queue.append(node.right) temp = max(rob1 + n, rob2) rob1 = rob2 rob2 = temp return rob2 return bfs()
I tried level order traversal and built an array list and then ran house robber 1 approach but it did not solve the edge cases. I hope one day I would be able to solve the way you do it!. Would you be able to explain what was your thought process to come to this solution
I was asked this question in an interview and I failed and I thought that it would use some complex data structure and algorithm, but your video proved me wrong! 😂 But honestly, thank you so much for explaining this!
I tried using House Robber I + BFS for this problem one, two = 0, 0 queue = [root] while queue -> num = 0 for _ in queue -> node = queue.popleft() queue.push(node.left) queue.push(node.right) num += node.data one, two = two, max(one + num, two) return two
Here's the code class Solution { public: pair help(TreeNode* root) { if(!root) return {0,0}; if(!root->left && !root->right) return{root->val,0}; return {root->val+help(root->left).second+help(root->right).second,(max(help(root->left).first,help(root->left).second)+max(help(root->right).first,help(root->right).second))}; } int rob(TreeNode* root) { return max(help(root).first,help(root).second); } }; It'd be great if someone could help
@@jorgemejia1586 But why can't we just set an variable, why should use a function? like we can just set n = 0 to change n why should we do it like def dfs(n) to change n?
for a skewed tree, level order traversal might not work. eg. 4 - 1 - 2 - 3 . level order will retun max 6 (4+2). but the robber can rob 4 and 3 and make a profit of 7
why cant you chose 4 and 100? They aren't directly connected. This is an ambigious question with no solution and you just wrote a solution of your own version of question.
It did not pass for me. I copied it exactly but does not pass :( class Solution: def rob(self, root: Optional[TreeNode]) -> int: # return pair: [withroot, withoutroot] def dfs(root): if not root: return [0, 0] leftPair = dfs(root.left) rightPair = dfs(root.left) withRoot = root.val + leftPair[1] + rightPair[1] withoutRoot = max(leftPair) + max(rightPair)
@@adityarathi3420 yeah I got the same but I used to think memoization is applied when we reapeatedly reach a given state in recursion. In this however we will traverse every node for once and there is no repeated state so why is there a need to memoize ? am I missing something ?
why is BFS not working here? given below is my code: if not root: return root q = deque([root]) res = [] while q: val = [] for i in range(len(q)): node = q.popleft() val.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(val) rob1, rob2 = 0, 0 for i in range(len(res)): if not i % 2: rob1 += sum(res[i]) else: rob2 += sum(res[i]) return max(rob1, rob2)
🌲 Tree Playlist: th-cam.com/video/OnSn2XEQ4MY/w-d-xo.html
Out of all the leetcode solutions on TH-cam, you write the cleanest, most understandable code. Please keep up the excellent work
Not everyone has the ability to teach brother you have it. keep enlightening us. !!
your way of solving problem especially building from scratch and your explanation is very clear and good .please do more videos on most solved leetcode problems.
Im dying at the corresponding number of Macauley Culkins in your House Robber series thumbnails, its just *chefs kiss*
It is incredible how comprehensible and organized your explanations and solutions are. Thank you so much!
I just want to add a comment for people who might not understand thoroughly. We are not simply skipping child nodes and reaching grandchild nodes. The max() here means we are carried over the largest value of the subtree with the grandchild node as the root for each grant child root. That is amazing. Thank a ton
If dfs results on nodes could be cached, the solution would be more straightforward. Instead of using cache, dfs results are broken down to avoid repeated dfs on children nodes. A smart workaround but it takes some time to figure out.
This playlist is absolute gold. Don't know what I will expect in DP and Graphs.
Thanks!
There is so much work behind the video of choosing the right test cases to give the explanations in the best way. Thanks for your efforts. You rock !
I really think whoever proposes this problem is definitely a genius! Such a problem with dfs, binary tree and dp, what a combination!
Love it ! Elegant and the way you write your code with few lines at the bottom , few lines in the middle like finishing a puzzle. It's beautiful.
Thanks so much! Ur videos have been helped me a lot. #1 channel on my list for leetcode study. Looking forward to see more of your videos!
Very Nice and Simplified explanation . Really appreciate your work.
I feel that this problem requires the combination of Dynamic Programming and DFS (Recursion), and you explained this problem very clearly. Even though I am using Java and you are using Python, I followed your logic and did this problem correctly. Thank you very much for your fantastic teaching and explanation!
Great Explaination. Loved it. Have been watching your videos for the past 2 months. This explaination forced me to do away with my laziness and comment.
Dude, this is some rockstar level content really. I can’t tell how grateful I’m and how motivating these are! Thanks a lot!
Beautifully explained. Thanks!
Bfs, store sum at each level and then just find max using alternate cells (0,2,4,...) (1,3,5,...). O(n) mem and O(n) time.
This is what I thought as well
This won't work for something like [2, 1, 3, null, 4]. Answer should be 7. This approach will return 6
@@alokesh985 nice one
I did it using bfs, borrowing from the solution to House Robber II
from collections import deque
class Solution:
def rob(self, root) -> int:
def bfs():
rob1, rob2 = 0, 0
queue = deque()
queue.append(root)
while queue:
n = 0
for i in range(len(queue)): # level order
node = queue.popleft()
n += node.val
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
temp = max(rob1 + n, rob2)
rob1 = rob2
rob2 = temp
return rob2
return bfs()
I start watching your channel when it was at 90k and now it's 95k ,(in approx. 1 month) ..Congratulation
Are you fr? I thought I couldn't solve this problem until I saw your explanation. Thanks for making an impact 🙌
I tried level order traversal and built an array list and then ran house robber 1 approach but it did not solve the edge cases.
I hope one day I would be able to solve the way you do it!.
Would you be able to explain what was your thought process to come to this solution
This channel is the real leetcode premium
not enough circling at 8:00, failed to understand
Very nice, thanks
You are just amazing 😭❤️
Amazing solution
Thank you very much! This was really good
Thanks! very great explanation!
Thank you for the great explanation!
thank you so much bro. You gave an excellent explanation.
I was asked this question in an interview and I failed and I thought that it would use some complex data structure and algorithm, but your video proved me wrong! 😂 But honestly, thank you so much for explaining this!
What interview did you have?
@@shaksham.22 Rippling
what will be the time complexity and space complexity of this algo?
BEAUTIFUL SOLUTION
Great explanation!!!
I tried using House Robber I + BFS for this problem
one, two = 0, 0
queue = [root]
while queue ->
num = 0
for _ in queue ->
node = queue.popleft()
queue.push(node.left)
queue.push(node.right)
num += node.data
one, two = two, max(one + num, two)
return two
Very well explained!!! .
Amazing, really helpful, thank you!!!
Thank you
Please can you increase the frequency i.e can you do more questions?
For this input [2,1,3,null,4] ans is given as 7. Isn't it 6
tree : 2
1 3
4
such clear explanation
This approach is giving TLE in C++
Here's the code
class Solution {
public:
pair help(TreeNode* root)
{
if(!root) return {0,0};
if(!root->left && !root->right) return{root->val,0};
return {root->val+help(root->left).second+help(root->right).second,(max(help(root->left).first,help(root->left).second)+max(help(root->right).first,help(root->right).second))};
}
int rob(TreeNode* root)
{
return max(help(root).first,help(root).second);
}
};
It'd be great if someone could help
@@anshhchaturvedi1155
class Solution {
public:
vector func(TreeNode* root){
if(root == NULL) return {0, 0};
vector leftPair = func(root->left);
vector rightPair = func(root->right);
int withRoot = root->val + leftPair[1] + rightPair[1];
int withoutRoot = max(leftPair[0], leftPair[1]) + max(rightPair[0], rightPair[1]);
return {withRoot, withoutRoot};
}
int rob(TreeNode* root) {
vector result = func(root);
return max(result[0], result[1]);
}
};
Will this solution be enough in an interview
U a God
great explaination
Awesome content. can you cover some segment tree problems in future videos
one question: when should we build a new nested funtion?
when you wanna pass a parameter that isn't given by the parent function
@@jorgemejia1586 But why can't we just set an variable, why should use a function?
like we can just set n = 0 to change n
why should we do it like def dfs(n) to change n?
what does leftPair[1] and rightPair[1] even mean? The left most left node at the end of the binary tree?
it represents the maximum score the robber can get if he decides not to rob the root node
Can we do level order traversal on this
for a skewed tree, level order traversal might not work. eg. 4 - 1 - 2 - 3 . level order will retun max 6 (4+2). but the robber can rob 4 and 3 and make a profit of 7
Can we solve it using BFS ?
beautiful
Nice thumbnail
the most perfect ever.
Thanks you sir! :-)
Smooth like Vaseline.
recursion makes problems easy af
Prabhu to the rescue!! _/\_
Is it possible to solve this in an interview without coming across it even once? 🧐
yeah
why cant you chose 4 and 100? They aren't directly connected. This is an ambigious question with no solution and you just wrote a solution of your own version of question.
Picasso 🤏🤏
OMG ! genius
god right here people
bro i thought you could use bfs on this one
It did not pass for me. I copied it exactly but does not pass :(
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
# return pair: [withroot, withoutroot]
def dfs(root):
if not root:
return [0, 0]
leftPair = dfs(root.left)
rightPair = dfs(root.left)
withRoot = root.val + leftPair[1] + rightPair[1]
withoutRoot = max(leftPair) + max(rightPair)
return [withRoot, withoutRoot]
return max(dfs(root))
rightPair = dfs(root.left) this should be
rightPair = dfs(root.right)
when a teacher unlocks his god-level mode 🤯
🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Why are we helping the thief?
'The thief realized it forms a binary tree' wtf is this shit lmao
please start coding in c++
class Solution {
public:
map map ;
int rob(TreeNode* root) {
if(not root) return 0 ;
if(map.count(root)) return map[root] ;
int withoutRoot = rob(root->left) + rob(root->right) ;
int withRoot = root->val ;
if(root->left) withRoot += rob(root->left->left) + rob(root->left->right) ;
if(root->right) withRoot += rob(root->right->left) + rob(root->right->right) ;
return map[root] = max(withRoot,withoutRoot) ;
}
};
@@adityarathi3420 Hi , why is memoization needed ??? what is the repeated step here ?
@@shivansh-gup without memoization i will getting tle on leetcode.
@@adityarathi3420 yeah I got the same but I used to think memoization is applied when we reapeatedly reach a given state in recursion. In this however we will traverse every node for once and there is no repeated state so why is there a need to memoize ? am I missing something ?
why is BFS not working here?
given below is my code:
if not root:
return root
q = deque([root])
res = []
while q:
val = []
for i in range(len(q)):
node = q.popleft()
val.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(val)
rob1, rob2 = 0, 0
for i in range(len(res)):
if not i % 2:
rob1 += sum(res[i])
else:
rob2 += sum(res[i])
return max(rob1, rob2)
Great Explaination