5:18 "There's no magic way; it's not just going to magically pop up into your mind, so DON'T BE LAZY; get a piece of paper, draw out some examples, and see what you can come up with." GOLDEN WORDS... I was too lazy and came to look up at the video to see solution without trying much, Thank You NeetCode, this really was a motivation that stirred my ego and I ended up doing the first problem with 100.00% better in time... Lots of love and respect to you Navdeep!!
This problem is even easier by following post order traversal get left node get right node check if root needs to be removed if yes, null check and add two children to roots list and return null else return node This way we don't need to maintain two sets TreeNode dfs(TreeNode root) { if(root == null) return null; TreeNode left = dfs(root.left); TreeNode right = dfs(root.right); if(nodesToDelete.contains(root.val)) { if(left != null) trees.add(left); if(right != null) trees.add(right); return null; } root.left = left; root.right = right; return root; }
As long as it's not a hard problem I can usually pump these out fast. As difficult it is to solve a LC hard, it's even more time consuming to explain them tbh
class Solution: def delNodes(self, r: Optional[TreeNode], t: List[int]) -> List[TreeNode]: t,o=set(t),[] def f(p): if p: p.left,p.right=f(p.left),f(p.right) if p.val not in t:return p o.extend((p.left,p.right)) o.append(f(r)) return [p for p in o if p]
Hi, man great explanation as always ❤. I'm new to leetcode I have been solving some easy problems on my own but I can not even sometimes solve an easy problem. Sometimes I can even come up with the logic but I can not code it out. (I am using java.) Can you please guide me how can I get better at coding and finding solutions of tough problems.
my solution, same idea but less concise: delete = set(to_delete) res = [] if root.val not in delete: res.append(root) def dfs(node, parentDeleted): if not node: return False if node.val in delete: dfs(node.left, True) dfs(node.right, True) return True if parentDeleted: res.append(node) if dfs(node.left, False): node.left = None if dfs(node.right, False): node.right = None return False dfs(root, False) return res
I am thinking if this solution misses some cases. If we have a tree like [1,2,3,4,5], to_delete is [4,5], is this solution going to work? In this case, 4 is deleted first, the child of 4(5) doesn’t have a chance to be checked? Because 4 is changed to point to None.
This is what I coded up. Simultaneous addition if its not to be deleted. Also didn't add everything and delete it. class Solution: def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]: to_delete = set(to_delete) roots = [] if root.val not in to_delete: roots.append(root) def dfs(node, par): nonlocal roots if node.val in to_delete: if node.left and node.left.val not in to_delete: roots.append(node.left) if node.right and node.right.val not in to_delete: roots.append(node.right) if par: if par.left and par.left.val == node.val: par.left = None else: par.right = None if node.left: dfs(node.left, node) if node.right: dfs(node.right, node)
class Solution: def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]: res=[] to_delete=set(to_delete) def dfs(root): if not root: return False result=dfs(root.left) if result: if root.left.left: res.append(root.left.left) if root.left.right: res.append(root.left.right) root.left=None result=dfs(root.right) if result: if root.right.left: res.append(root.right.left) if root.right.right: res.append(root.right.right) root.right=None if root.val in to_delete: return True return False result=dfs(root) if result: if root.left: res.append(root.left) if root.right: res.append(root.right) else: res.append(root) return res
My code for this question is very long and ugly. As a tree problem, the code should not be so long. I just came here to confirm that this question is really that disgusting, and it seems that I was right.
A simple BFS solution in your style, is it? class Solution: def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]: target = set(to_delete) if not target: return [root] res = [] if root.val not in target: res.append(root) curr = TreeNode(-1, root) q = deque([curr]) while q: node = q.popleft() if node.left: q.append(node.left) if node.left and node.left.val in target: node.left = None
if node.right: q.append(node.right) if node.right and node.right.val in target: node.right = None
if node.val in target: if node.left and node.left.val not in target: res.append(node.left) if node.right and node.right.val not in target: res.append(node.right)
// My JS solution using top-down deletion and collection var delNodes = function (root, to_delete) { to_delete = new Set(to_delete) const res = [] function dfs(node, parent) { if (!node) return let newParent = null // if node is deleted then it's children has no parent if (to_delete.has(node.val)) { if (parent) { if (parent?.left?.val === node.val) parent.left = null else parent.right = null } } else { if (!parent) res.push(node) newParent = node } dfs(node.left, newParent) dfs(node.right, newParent) } dfs(root, null) return res };
5:18 "There's no magic way; it's not just going to magically pop up into your mind, so DON'T BE LAZY; get a piece of paper, draw out some examples, and see what you can come up with."
GOLDEN WORDS... I was too lazy and came to look up at the video to see solution without trying much, Thank You NeetCode, this really was a motivation that stirred my ego and I ended up doing the first problem with 100.00% better in time... Lots of love and respect to you Navdeep!!
Solved it by myself in O(n) space and O(n) time. Thank you for teaching me Navdeep! I am better than my past self because of NeetCode. Thank you!!
This problem is even easier by following post order traversal
get left node
get right node
check if root needs to be removed if yes, null check and add two children to roots list and return null else return node
This way we don't need to maintain two sets
TreeNode dfs(TreeNode root) {
if(root == null) return null;
TreeNode left = dfs(root.left);
TreeNode right = dfs(root.right);
if(nodesToDelete.contains(root.val)) {
if(left != null) trees.add(left);
if(right != null) trees.add(right);
return null;
}
root.left = left;
root.right = right;
return root;
}
I haven't practiced trees in a while but happy that the daily is making me revise old topics.
Same for me.
First! Love super early videos these days. Will start reading the neetcode new chapter tonight.
As long as it's not a hard problem I can usually pump these out fast.
As difficult it is to solve a LC hard, it's even more time consuming to explain them tbh
@@NeetCodeIO for hard one, sometime I could not figure them out until watching your videos 😅
@@NeetCodeIO what type of traversal is your solution preorder or postorder ?
I got a 70 line solution in java, did use like 2 sets, but got last pos on leetcode even on O(n)😢
Unlike others but in Java i almost everytime get 0ms its sp satisfying... and you might cross check your code for unnecessary checks and iterations
class Solution:
def delNodes(self, r: Optional[TreeNode], t: List[int]) -> List[TreeNode]:
t,o=set(t),[]
def f(p):
if p:
p.left,p.right=f(p.left),f(p.right)
if p.val not in t:return p
o.extend((p.left,p.right))
o.append(f(r))
return [p for p in o if p]
Sovled it on my own. I found these daily questions best to practise DSA questions and revise my concept.
I was hoping you would make a video, thanks
Gosh I hate recursive calls. Solved with while loop using some extra space to check if node has parents (meaning is not disjointed)
Nice question 🎉
Hi, man great explanation as always ❤.
I'm new to leetcode I have been solving some easy problems on my own but I can not even sometimes solve an easy problem. Sometimes I can even come up with the logic but I can not code it out. (I am using java.) Can you please guide me how can I get better at coding and finding solutions of tough problems.
my solution, same idea but less concise:
delete = set(to_delete)
res = []
if root.val not in delete: res.append(root)
def dfs(node, parentDeleted):
if not node:
return False
if node.val in delete:
dfs(node.left, True)
dfs(node.right, True)
return True
if parentDeleted:
res.append(node)
if dfs(node.left, False):
node.left = None
if dfs(node.right, False):
node.right = None
return False
dfs(root, False)
return res
Stack, tree and forest 🎉🎉🎉
Thank you
Would the space complexity not be O(n+m) because of the two hashsets?
Great explanation as always. Thank you
Bruhh just love your consistency in posting every solutions for the problem of the day. Keep going bruhh LOVE YOU😇🤗
sorry for the oot, but what tools did you use when drawing the algorithm ?
Looks like one note to me
its so sad the only problem i missed is "maximum score from removing substring" because i misinterpreted it 😭
I am thinking if this solution misses some cases. If we have a tree like [1,2,3,4,5], to_delete is [4,5], is this solution going to work? In this case, 4 is deleted first, the child of 4(5) doesn’t have a chance to be checked? Because 4 is changed to point to None.
This is what I coded up. Simultaneous addition if its not to be deleted. Also didn't add everything and delete it.
class Solution:
def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
to_delete = set(to_delete)
roots = []
if root.val not in to_delete:
roots.append(root)
def dfs(node, par):
nonlocal roots
if node.val in to_delete:
if node.left and node.left.val not in to_delete:
roots.append(node.left)
if node.right and node.right.val not in to_delete:
roots.append(node.right)
if par:
if par.left and par.left.val == node.val:
par.left = None
else:
par.right = None
if node.left:
dfs(node.left, node)
if node.right:
dfs(node.right, node)
dfs(root, None)
return roots
hey can you post the iterative solution somewhere i can do the recursive bet cant do iterative
class Solution:
def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
res=[]
to_delete=set(to_delete)
def dfs(root):
if not root:
return False
result=dfs(root.left)
if result:
if root.left.left:
res.append(root.left.left)
if root.left.right:
res.append(root.left.right)
root.left=None
result=dfs(root.right)
if result:
if root.right.left:
res.append(root.right.left)
if root.right.right:
res.append(root.right.right)
root.right=None
if root.val in to_delete:
return True
return False
result=dfs(root)
if result:
if root.left:
res.append(root.left)
if root.right:
res.append(root.right)
else:
res.append(root)
return res
Bro doesn't miss
class Solution {
public:
vector res;
unordered_set del;
void dfs(TreeNode *&root) {
if (root == NULL) return;
dfs(root->left);
dfs(root->right);
if (del.find(root->val) != del.end()) {
if (root->left) res.push_back(root->left);
if (root->right) res.push_back(root->right);
root = NULL;
delete root;
}
}
vector delNodes(TreeNode *root, vector &to_delete) {
for (int i = 0; i < to_delete.size(); i++) {
del.insert(to_delete[i]);
}
dfs(root);
if (root) res.push_back(root);
return res;
}
};
This wasn't super tough, but then had some edge cases..
cute problem 🥰
My code for this question is very long and ugly. As a tree problem, the code should not be so long. I just came here to confirm that this question is really that disgusting, and it seems that I was right.
I might be wrong but it looks like the deleted nodes are still connected to theirs children even though the result still satisfied.
A simple BFS solution in your style, is it?
class Solution:
def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
target = set(to_delete)
if not target: return [root]
res = []
if root.val not in target:
res.append(root)
curr = TreeNode(-1, root)
q = deque([curr])
while q:
node = q.popleft()
if node.left:
q.append(node.left)
if node.left and node.left.val in target:
node.left = None
if node.right:
q.append(node.right)
if node.right and node.right.val in target:
node.right = None
if node.val in target:
if node.left and node.left.val not in target:
res.append(node.left)
if node.right and node.right.val not in target:
res.append(node.right)
return res
A simple recursive java solution
class Solution {
private List trees = new ArrayList();
private TreeNode helper(TreeNode root, Set to_delete){
if(root == null){
return null;
}
TreeNode leftTree = helper(root.left, to_delete);
TreeNode rightTree = helper(root.right, to_delete);
if(to_delete.contains(root.val)){
if(leftTree != null) trees.add(leftTree);
if(rightTree != null) trees.add(rightTree);
return null;
}
root.left = leftTree;
root.right = rightTree;
return root;
}
public List delNodes(TreeNode root, int[] to_delete) {
Set del = new HashSet();
for( var i : to_delete ){
del.add(i);
}
TreeNode node = helper(root, del);
if(node != null){
trees.add(node);
}
return trees;
}
}
// My JS solution using top-down deletion and collection
var delNodes = function (root, to_delete) {
to_delete = new Set(to_delete)
const res = []
function dfs(node, parent) {
if (!node) return
let newParent = null
// if node is deleted then it's children has no parent
if (to_delete.has(node.val)) {
if (parent) {
if (parent?.left?.val === node.val) parent.left = null
else parent.right = null
}
} else {
if (!parent) res.push(node)
newParent = node
}
dfs(node.left, newParent)
dfs(node.right, newParent)
}
dfs(root, null)
return res
};
@neetcode
Why is the java equivalent of the above code not working?
class Solution {
HashSet delSet = new HashSet();
HashSet resSet = new HashSet();
List res = new ArrayList();
// DFS , Hashset
public List delNodes(TreeNode root, int[] to_delete) {
for(int n: to_delete){
delSet.add(n);
}
dfs(root);
for(TreeNode node: resSet){
res.add(node);
}
return res;
}
public TreeNode dfs(TreeNode node){
if(node == null){return null;}
TreeNode res = node;
if(delSet.contains(node.val)){
res = null;
resSet.remove(node);
if(node.left != null){
resSet.add(node.left);
}
if(node.right != null){
resSet.add(node.right);
}
}
node.left = dfs(node.left);
node.right = dfs(node.right);
return res;
}
}
what type of traversal is this @NeetCodeIO
Post Order.
Post Order.