Delete Leaves With a Given Value - Leetcode 1325

Delete Leaves With a Given Value - Leetcode 1325 - Python

Рет қаралды 6,805

NeetCodeIO

Күн бұрын

Пікірлер: 23

@kareni7572 5 ай бұрын

Yes, The leaf node check should be done post order (not pre order) -- so that it will reach till parent

@krateskim4169 6 ай бұрын

Ayo the thumbnail😂

@Pegasus02Kr 6 ай бұрын

honestly I doubt we will ever have chance to implement tree traversal with iterative approach... thanks for the explanation

@MP-ny3ep 6 ай бұрын

Thank you so much for the daily problems.

@Ari-pq4db 6 ай бұрын

Thank You 🍃

@DeathSugar 6 ай бұрын

Dunno why is it medium. Pretty straightforward solution.

@chrischika7026 6 ай бұрын

look at the iterative.

@DeathSugar 6 ай бұрын

@@chrischika7026 uglier and complicated, more memory footprint and not really outperforms recursive one. Would work on the languages which has no recursion, but they aren't on the language list in leetcode anyway, so why bother?

@NursultanBegaliev 6 ай бұрын

Thank you!

@jayberry6557 6 ай бұрын

Is there any reason why would we use bfs in this case?

@staywithmeforever 6 ай бұрын

We can use dfs also no problem.

@staywithmeforever 6 ай бұрын

But if you wanna use bfs u need parent pointers that will be complicated.

@staywithmeforever 6 ай бұрын

U have to make a while look and keep on deleting the parents while target!=root.val. so this makes O(n2)

@nirmalgurjar8181 6 ай бұрын

Accepted Java Iterative Solution using map and stack: class Solution { public TreeNode removeLeafNodes(TreeNode root, int target) { Map parentMap = new HashMap(); Stack stk = new Stack(); stk.push(root); while (!stk.isEmpty()) { TreeNode node = stk.pop(); if (node.right == null && node.left == null && node.val == target) { // delete this node TreeNode parent = parentMap.get(node); if (parent != null && parent.right == node) { // update parent right pointer to null parentMap.remove(node); parent.right = null; } if (parent != null && parent.left == node) { // update parent left pointer to null parentMap.remove(node); parent.left = null; } } else { boolean added = false; if (node.right != null && !parentMap.containsKey(node.right)) { added = true; stk.push(node); // add back current node to stack stk.push(node.right); parentMap.put(node.right, node); } if (node.left != null && !parentMap.containsKey(node.left)) { if (!added) { stk.push(node); // if not added ealier then add back } stk.push(node.left); parentMap.put(node.left, node); } } } //if root only is pending and having value == target if (root.left == null && root.right == null && root.val == target) { return null; } return root; } }