Convert BST to Greater Tree - Leetcode 538 - 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/convert...
0:00 - Read the problem
1:05 - Drawing Explanation
5:34 - Coding Explanation
leetcode 538
#amazon #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. 
Наука
Hey man I just want to say thanks for all you do for the community. I landed my dream job at Microsoft and your channel was a big part of me building up my DSA foundations. Everybody out there keep practicing these problems I swear it'll pay off in the long run
Thanks
Hey, I've a request can you make new series on minimal dsa concepts (required for solving problems and understanding concepts) using python.
Guys like this comment if you want it too(it'll appear on top and he'll read it hopefully 😅)
It took me waaay too long to find the solution but for what it is worth, you don't need a tmp variable if you do an assignment:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
prev = 0
def dfs(node):
nonlocal prev
if node:
dfs(node.right,)
node.val += prev
prev= node.val
dfs(node.left)
dfs(root)
return root
Thanks! Very awesome videos! If you have google code jam tutorial, not just for leetcode, I would definitely join the member channel!
Nice explanation as always! Do you mind doing "307. Range Sum Query - Mutable" or "37. Sudoku Solver" or something about A* someday? It will force me to do them :S i mean you already managed to make me do KMP and the daily leetcode challenges, what is a few more good deeds?
You could just use : curSum+=node.val
node.val=curSum
Good point!
Great explanation as always. You don't really need to mention curSum as nonlocal or have a tmp variable actually:
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
curSum = [0]
def dfs(root):
if not root : return
dfs(root.right)
root.val += curSum[0]
curSum[0] = root.val
dfs(root.left)
dfs(root)
return root
Great expleniation, and which app do you use to drawing?
God damn so easy but just tricky enough. Thanks for the vid.
Hi Neetcode, thanks for your amazing explanations. cannot think of solving DSA with out your videos. thanks for making it possible for me. i have a request. is it possible for u to create playlists based on companies ?
Really nice
what app do you use to record screen and for white board?
We can also Pass the curSum as a member variable in the Constructor initialize part. Then inside DFS we don't need to mention curSum as global variable.
Yo which language do you recommend for competitive programming because everyone says pythons not good for that
The opposite happened to me, I have my work experience in Python, but when the interviewer gave me questions to solve, I chose C++
Then he asked, why you choose C++ when you have X years of experience in Python
Hello Neetcode, thank you for these great videos and your explanation. Could you please share with us what drawing tablet do you use and what software do you use for video editing? Thank you and I am eagerly waiting for your new videos!
King.
hey there NeetCode, love your channel its really bright and understandable!
can you make a video on:
1202. Smallest String With Swaps?
there are coupe of videos on youtube but i didnt quite understand their explanations.
If you want, we could use a list to store the curSum, and modify it in the nested function, Cause it is a shallow copy. And no need to store the tmp.
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
curSum = [0]
def dfs(node):
if not node:
return None
dfs(node.right)
'''
tmp = node.val
node.val += curSum[0]
curSum[0] += tmp
'''
node.val += curSum[0]
curSum[0] = node.val
dfs(node.left)
dfs(root)
return root
Can we make inorder traversal in original tree and stored in an array
After that with prifix logic sum we make another array in sorted manner
And with logic of makin bst with arr we can return new root
Sir need an explanation of Word break problem on lc
Didn't he already do that
💯✨
Let’s gooo
you can also solve this problem doing first inorder traversal and using after the technique of prefix sum .Here is my solution in c++
class Solution {
public:
void dfs_inorder(TreeNode* root, vector &v, vector &ans){
if (root != NULL){
dfs_inorder(root->left, v, ans);
ans.push_back(root);
v.push_back(root->val);
dfs_inorder(root->right, v, ans);
}
}
TreeNode* convertBST(TreeNode* root) {
if (root == NULL)
return NULL;
vector ans;
vector v;
dfs_inorder(root, v, ans);
for (int i=1;ival = v[n-1];
for (int i=1;ival = (v[n-1]-v[i-1]);
}
return root;
}
};
Postorder?
Nope. Postorder is left first, then right, and finally the middle node. This is actually reversed inorder traversal, which is right first, then middle node, and finally left.
@@jeremyliang7159 got it
Hey Neetcode, you could also eliminate temp by doing something like this(just carry the updated root.val as currSum for further iterations): Just a suggestion :). BTW, great work!
dfs(root.right)
root.val += currSum
currSum = root.val
The main catch of this problem is the part is updating the curSum 😴
I can't solve this😂
Thanks a lot for another video and amazing explanation. I'd like to ask you a favor though (or maybe a suggestion): it's often hard for me to see the key takeaway from the problem that would make me (us) go in the right direction for the solution, so something that would definitely help me (and possibly others) is to highlight (perhaps written in red with big font? :D) the key words we should keep in mind from your explanation. I usually struggle to find the right topic that would give me the optimal solution (should I use a hash map? a tree? only array manipulation? is it graph?) and then once I figure it out, I still have a hard time building up the solution idea.
I don't know if my description was clear enough (I hope so) but it doesn't matter, again, thanks a lot for your effort and videos (and recently your algo list at neetcode.io) and congrats for landing a job at Google.
All the best
Use self.curSum. I don't think tmp is necessary. U can do the calculation first "curSum+=node.val" then update the node "node.val=curSum". since the initial curSum is 0.
self.max=0
def dfs(root):
if not root:
return
dfs(root.right)
self.max+=root.val
root.val=self.max
dfs(root.left)
dfs(root)
return root