@aryanbhardwaj7519
For someone thinking about studying from mik , I would say this is the best resource for DSA , even better than striver at times. After studying from striver and now after watching graphs from mik , I've realised that striver teaches in a way that makes you think that you need to learn this approach whereas mik instills in you the approach without making you feel like it's a burden.
@gui-codes
Ye khud se solve hogaya MIK sir. Thanks a lot
@jeehub041
Maja aa gaya bhaiya one pass solution kya samjhaya ha aapne. 🙌🙌
@hypewaali
I did using 1st approach. 2nd approach was too good 👍
@shreyabajaj4588
class Solution {
List<Integer>list=new ArrayList<>();
public TreeNode replaceValueInTree(TreeNode root) {
solve(root);
solution(root);
return root;
}
private void solve(TreeNode root){
Queue<TreeNode>q=new LinkedList<>();
q.offer(root);
while(!q.isEmpty()){
int n=q.size();
int sum=0;
for(int i=0;i<n;i++){
TreeNode curr=q.poll();
sum+=curr.val;
if(curr.left!=null){
q.offer(curr.left);
}
if(curr.right!=null){
q.offer(curr.right);
}
}
list.add(sum);
}
}
private void solution(TreeNode root){
Queue<TreeNode>q=new LinkedList<>();
int j=0;
root.val=list.get(j)-root.val;
j++;
q.offer(root);
while(!q.isEmpty()){
int n=q.size();
for(int i=0;i<n;i++){
int sum=0;
TreeNode curr=q.poll();
if(curr.left!=null){
sum+=curr.left.val;
}
if(curr.right!=null){
sum+=curr.right.val;
}
if(curr.left!=null){
curr.left.val=list.get(j)-sum;
q.offer(curr.left);
}
if(curr.right!=null){
curr.right.val=list.get(j)-sum;
q.offer(curr.right);
}
}
j++;
}
}
}
@aws_handles
Hats off to the 2nd approach. Samajhne k baad bahot easy lag raha ye problem. Approach-1 was easy
@Playvish
Done it in two passes
class Solution {
public:
TreeNode* replaceValueInTree(TreeNode* root) {
//first find the level sum
vector<TreeNode *> currChild;
currChild.push_back(root);
vector<long long> levelSum;
while(!currChild.empty()){
vector<TreeNode *> nextChild;
int sum = 0;
for(TreeNode * node : currChild){
sum += node->val;
if(node->left!=0)
nextChild.push_back(node->left);
if(node->right!=0)
nextChild.push_back(node->right);
}
levelSum.push_back(sum);
currChild = nextChild;
}
vector<pair<TreeNode *,int>> cch;
cch.push_back({root,0});
int level = 0;
while(!cch.empty()){
vector<pair<TreeNode *,int>> nch;
for(auto i : cch){
TreeNode * node = i.first;
node->val = levelSum[level] - (node->val + i.second);
if(node->left!=0){
int sibling = node->right==0?0:node->right->val;
nch.push_back({node->left,sibling});
}
if(node->right!=0){
int sibling = node->left==0?0:node->left->val;
nch.push_back({node->right,sibling});
}
}
level++;
cch = nch;
}
return root;
}
};
@sohaibshaikh7208
DSA ka godfather == codestorywithMIK 😎
@RohitKumar-dz8dh
Thanks ☺
@AmarjeetKumar-to9ub
Thank You :)
@Its_Shubham_Negi
Hi bhaiya ! I'm having a doubt pls resolve it....I applied exactly the same concept( building the lvl sum array and then updating the node value to currLvlSum-sibling).....But here I used DFS instead of BFS, and it gave me a TLE..although my TC was O(n)...Can u plz help me!!
@PriyanshuTyagi-ts2uw
why have you added unnecessary while loop in bfs? n- - wala
@VineetDixit
brother plz adds kam krdo plz
@codestorywithMIK