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
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 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()
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
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
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!
@@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 ?
you are making it more complicated. You also draw too much and say tooooooo much. provide the idea first, then try to explain. This will make sense then. Otherwise, you are just trying to explain without giving how to do it and at last you tell this is the way you do it. That is not helping at all.
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: ua-cam.com/video/OnSn2XEQ4MY/v-deo.html
Out of all the leetcode solutions on UA-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. !!
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
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.
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.
This playlist is absolute gold. Don't know what I will expect in DP and Graphs.
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 !
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 really think whoever proposes this problem is definitely a genius! Such a problem with dfs, binary tree and dp, what a combination!
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!
Very Nice and Simplified explanation . Really appreciate your work.
Beautifully explained. Thanks!
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.
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!
Dude, this is some rockstar level content really. I can’t tell how grateful I’m and how motivating these are! Thanks a lot!
Are you fr? I thought I couldn't solve this problem until I saw your explanation. Thanks for making an impact 🙌
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
Very nice, thanks
This channel is the real leetcode premium
Amazing solution
Thank you very much! This was really good
Thanks! very great explanation!
not enough circling at 8:00, failed to understand
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]);
}
};
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
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
Very well explained!!! .
You are just amazing 😭❤️
Thank you
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
thank you so much bro. You gave an excellent explanation.
Thank you for the great explanation!
such clear explanation
Great explanation!!!
Amazing, really helpful, thank you!!!
great explaination
BEAUTIFUL SOLUTION
U a God
Awesome content. can you cover some segment tree problems in future videos
recursion makes problems easy af
Thanks!
Please can you increase the frequency i.e can you do more questions?
Will this solution be enough in an interview
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?
For this input [2,1,3,null,4] ans is given as 7. Isn't it 6
tree : 2
1 3
4
what will be the time complexity and space complexity of this algo?
Smooth like Vaseline.
Nice thumbnail
beautiful
the most perfect ever.
Can we solve it using BFS ?
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
Prabhu to the rescue!! _/\_
Thanks you sir! :-)
god right here people
Is it possible to solve this in an interview without coming across it even once? 🧐
yeah
bro i thought you could use bfs on this one
Why are we helping the thief?
Picasso 🤏🤏
OMG ! genius
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.
when a teacher unlocks his god-level mode 🤯
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)
'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 ?
you are making it more complicated. You also draw too much and say tooooooo much. provide the idea first, then try to explain. This will make sense then. Otherwise, you are just trying to explain without giving how to do it and at last you tell this is the way you do it. That is not helping at all.
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