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.
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 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!
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 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 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!
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 ?
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)
![[UNCUT]"ทักษิณ" โชว์ฤทธิ์-ครอบครอง "อุ๊งอิ๊ง" ประเทศไทยมีนายกฯ 1แถม1 I คนดังนั่งเคลียร์ I 23 ส.ค.67](http://i.ytimg.com/vi/Uyl4y59R-Sk/mqdefault.jpg)
![เบิ้ล ปทุมราช - สาวสอง ( มีมี่ของอ้าย ) ft. ตาต้า,ต้องเต [OFFICIAL MV]](http://i.ytimg.com/vi/mqlMjnP08XI/mqdefault.jpg)
🌲 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. !!
Im dying at the corresponding number of Macauley Culkins in your House Robber series thumbnails, its just *chefs kiss*
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 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.
It is incredible how comprehensible and organized your explanations and solutions are. Thank you so much!
This playlist is absolute gold. Don't know what I will expect in DP and Graphs.
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.
I really think whoever proposes this problem is definitely a genius! Such a problem with dfs, binary tree and dp, what a combination!
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!
Very Nice and Simplified explanation . Really appreciate your work.
Are you fr? I thought I couldn't solve this problem until I saw your explanation. Thanks for making an impact 🙌
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.
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!
This channel is the real leetcode premium
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()
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 start watching your channel when it was at 90k and now it's 95k ,(in approx. 1 month) ..Congratulation
Thank you very much! This was really good
Amazing solution
Very nice, thanks
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
thank you so much bro. You gave an excellent explanation.
Thanks! very great explanation!
Thank you for the great explanation!
Amazing, really helpful, thank you!!!
Great explanation!!!
Very well explained!!! .
such clear explanation
great explaination
U a God
BEAUTIFUL SOLUTION
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 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
Thanks!
Awesome content. can you cover some segment tree problems in future videos
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]);
}
};
Please can you increase the frequency i.e can you do more questions?
Will this solution be enough in an interview
Thanks you sir! :-)
what will be the time complexity and space complexity of this algo?
beautiful
Nice thumbnail
the most perfect ever.
recursion makes problems easy af
Smooth like Vaseline.
For this input [2,1,3,null,4] ans is given as 7. Isn't it 6
tree : 2
1 3
4
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 solve it using BFS ?
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?
Is it possible to solve this in an interview without coming across it even once? 🧐
yeah
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
OMG ! genius
when a teacher unlocks his god-level mode 🤯
god right here people
Picasso 🤏🤏
'The thief realized it forms a binary tree' wtf is this shit lmao
bro i thought you could use bfs on this one
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.
🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Why are we helping the thief?
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)
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)