Height of Binary Tree After Subtree Removal Queries | Leetcode 2458
ฝัง
- เผยแพร่เมื่อ 23 พ.ย. 2024
- This video explains finding the height of binary tree after subtree removal queries using the most optimal approach of preprocessing using simple DFS recursion using array or hashmap.
----------------------------------------------------------------------------------------------------------------------------------------------------------------
🟣 JOIN our 𝐋𝐈𝐕𝐄 𝐢𝐧𝐭𝐞𝐫𝐯𝐢𝐞𝐰 𝐭𝐫𝐚𝐢𝐧𝐢𝐧𝐠 𝐩𝐫𝐨𝐠𝐫𝐚𝐦 through whatsapp query: +91 8918633037
🟣 𝐂𝐡𝐞𝐜𝐤𝐨𝐮𝐭 𝐚𝐥𝐥 𝐨𝐮𝐫 𝐂𝐨𝐮𝐫𝐬𝐞𝐬: techdose.co.in/
🔵 LinkedIn: / surya-pratap-kahar
🔴 INSTAGRAM: / techdose_official
🟢 𝐓𝐞𝐜𝐡𝐝𝐨𝐬𝐞-𝟏𝟎𝟎 𝐬𝐡𝐞𝐞𝐭: docs.google.co...
---------------------------------------------------------------------------------------------------------------------------------------------------------------
𝐂𝐎𝐃𝐄 𝐋𝐈𝐍𝐊: gist.github.co...
![[MV] A leap of faith...ความเชื่อใจครั้งสุดท้าย (From "Petrichor the series")](http://i.ytimg.com/vi/U1piZH2CNXA/mqdefault.jpg)
Generally, I watch all technical videos at a playback speed of 1.5x, but when it comes to yours, I prefer to watch at normal speed because I want to catch every word.
When you explain complex problems, you break them down into simple terms, making it feel like you're telling a straightforward story. 😍
Thank you so much! 👍
welcome :)
You really deserve some recognition. Amazing explanation.
thanks for your kind appreciation :)
Superb efforts sir definitely one of the top dsa mentor
🙏🏼
this was an absolutely fantastic video, thank you
welcome 🤗
Yup, next striver!!!!
The only problem is that, he gave answer from editorial instead of own.
however, he explained well.
Thank you so much sir . This is helpful !
Glad it helped! 😄
Very detailed Explination.
:)
Superb explanation !!
thanks :)
Amazing explanation.
Thanks :)
Amazing explanation!!!!
finally solved it aa ?
Thanks, now i can understand the idea of solution this problem. It was really helpful! Though you use C++, I was able to write the algorithm in python anyway, you really nicely explain the idea!
nice :)
Explained well.
Thanks :)
Nice explanation
Thanks :)
great explination
Thanks :)
Not able to wrap my head around why top 2 heights are used. Let's say at the current level (l3) there are 4 nodes (a,b,c,d) and all of them have the max-ht of 10.
Now if the query is [a,b,c,d] and l3 stores only 2 top heights (say a & b's height are stored) then what will happen to 'c' and 'd' queries ?
The queries are all independent. Moreover, the problem just asks about finding height and it doesnt matter which node we choose as long as we are Greedily choosing the node with max ht :)
In the worst case, the node removed will be the one with max ht. In that case it is always optimal to greedily choose 2nd best option ELSE we will always choose max ht at that level.
@@techdose4u damn i missed a part of the question (independent queries) and successfully wasted 2-3 hrs :(
Thanks a lot for the insight
Thank you !
welcome :)
Hi, Why didn't you use 0 based values for storing the heights??
If you had done that like you did for storing the levels, then you didn't need to subtract 1 at last while returning answer...
You can do 0 based or 1 based.
But I follow a standard across all problems to take 1-based counting hence its my personal bias :)
@@techdose4u Yeah, I tried with 0 biased and it worked fine :)
How did we get 1 second = 10^8 operations?
just a standard which coding platforms use and expectations which work in OAs.
Does anyone know the name of the software he uses to draw?
dimaag ka bhosda hogya dekh k
i hate coding
i hate dsa
but i did it
i survived another day doing dsa
thanks
25/40 passed idk why...
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
int findmax(TreeNode* curr, int level, vector& node_level,
vector& node_height, vector& top2_ht) {
if (!curr)
return 0;
// recursively we find the ht of the subtrees
int ht = 1 + max(findmax(curr->left, level + 1, node_level, node_height,
top2_ht),
findmax(curr->right, level + 1, node_level,
node_height, top2_ht));
node_level[curr->val] = level;
node_height[curr->val] = ht;
if (ht > top2_ht[level].first) {
top2_ht[level].first = ht;
} else if (ht > top2_ht[level].second) {
top2_ht[level].second = ht;
}
return ht;
}
vector treeQueries(TreeNode* root, vector& queries) {
int n = 100001;
vector node_level(n, -1);
vector node_height(n, 0);
vector top2_ht(n, {0, 0});
findmax(root, 0, node_level, node_height, top2_ht);
vector res;
for (int query_node : queries) {
int level = node_level[query_node];
int ht = node_height[query_node];
int maxi = (top2_ht[level].first == ht) ? top2_ht[level].second : top2_ht[level].first;
// if (top2_ht[level].first == ht && top2_ht[level].second > 0) {
// maxi = top2_ht[level].second;
// } else {
// maxi = top2_ht[level].first;
// }
res.push_back(maxi + level - 1);
}
return res;
}
};
can you please match it with my code in C++.
Your code is similar. It should help you identify something which may not be visible right away.
if (ht > top2_ht[level].first) {
top2_ht[level].first = ht; // here update of second need to done
} else if (ht > top2_ht[level].second) {
top2_ht[level].second = ht;
}check this snippet once go through the logic of largest 2 numbers in a array in single pass
update second top height to first top height when you find a height greater than first height
if (ht > top2_ht[level].first) {
top2_ht[level].first = ht;
} else if (ht > top2_ht[level].second) {
top2_ht[level].second = ht;
}
In this, u need to update top2_ht[level].second = top2_ht[level].first if ht > top2_ht[level].first