Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1110.html

1110. Delete Nodes And Return Forest (Medium)

Given the root of a binary tree, each node in the tree has a distinct value.

After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).

Return the roots of the trees in the remaining forest.  You may return the result in any order.

 

Example 1:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

 

Constraints:

  • The number of nodes in the given tree is at most 1000.
  • Each node has a distinct value between 1 and 1000.
  • to_delete.length <= 1000
  • to_delete contains distinct values between 1 and 1000.

Related Topics:
Tree, Depth-first Search

Solution 1.

  • /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
            if (root == null)
                return new ArrayList<TreeNode>();
            Set<Integer> deleteSet = new HashSet<Integer>();
            for (int value : to_delete)
                deleteSet.add(value);
            List<TreeNode> nodesList = new ArrayList<TreeNode>();
            Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                nodesList.add(node);
                TreeNode left = node.left, right = node.right;
                if (left != null) {
                    map.put(left, node);
                    queue.offer(left);
                }
                if (right != null) {
                    map.put(right, node);
                    queue.offer(right);
                }
            }
            List<TreeNode> forest = new ArrayList<TreeNode>();
            if (!deleteSet.contains(root.val))
                forest.add(root);
            for (int i = nodesList.size() - 1; i >= 0 && !deleteSet.isEmpty(); i--) {
                TreeNode node = nodesList.get(i);
                if (deleteSet.contains(node.val)) {
                    TreeNode parent = map.get(node);
                    if (parent != null) {
                        if (node == parent.left)
                            parent.left = null;
                        else if (node == parent.right)
                            parent.right = null;
                    }
                    TreeNode left = node.left, right = node.right;
                    if (left != null)
                        forest.add(left);
                    if (right != null)
                        forest.add(right);
                    deleteSet.remove(node.val);
                }
            }
            return forest;
        }
    }
    
    ############
    
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
            boolean[] del = new boolean[1001];
            for (int d : to_delete) {
                del[d] = true;
            }
            List<TreeNode> res = new ArrayList<>();
            dfs(root, true, del, res);
            return res;
        }
    
        private TreeNode dfs(TreeNode root, boolean isRoot, boolean[] del, List<TreeNode> res) {
            if (root == null) {
                return null;
            }
            boolean flag = del[root.val];
            if (!flag && isRoot) {
                res.add(root);
            }
            root.left = dfs(root.left, flag, del, res);
            root.right = dfs(root.right, flag, del, res);
            return flag ? null : root;
        }
    }
    
  • // OJ: https://leetcode.com/problems/delete-nodes-and-return-forest/
    // Time: O(N)
    // Space: O(D + H)
    class Solution {
        vector<TreeNode*> ans;
        unordered_set<int> s;
        void dfs(TreeNode *root, TreeNode *p = NULL) {
            if (!root) return;
            dfs(root->left, root);
            dfs(root->right, root);
            if (s.count(root->val)) {
                if (p != NULL) {
                    if (p->left == root) p->left = NULL;
                    else p->right = NULL;
                }
                if (root->left) ans.push_back(root->left);
                if (root->right) ans.push_back(root->right);
            } else if (p == NULL) ans.push_back(root);
        }
    public:
        vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
            s = unordered_set<int>(begin(to_delete), end(to_delete));
            dfs(root);
            return ans;
        }
    };
    
  • # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
            def dfs(fa, root):
                if root is None:
                    return
                dfs(root, root.left)
                dfs(root, root.right)
                if root.val in s:
                    if fa and fa.left == root:
                        fa.left = None
                    if fa and fa.right == root:
                        fa.right = None
                    if root.left:
                        ans.append(root.left)
                    if root.right:
                        ans.append(root.right)
    
            s = set(to_delete)
            ans = []
            if root.val not in s:
                ans.append(root)
            dfs(None, root)
            return ans
    
    ############
    
    # 1110. Delete Nodes And Return Forest
    # https://leetcode.com/problems/delete-nodes-and-return-forest/
    
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
            res = []
            delete = set(to_delete)
            
            def dfs(node, is_root):
                if not node: return None
                
                to_delete = node.val in delete
                
                if is_root and not to_delete:
                    res.append(node)
                
                node.left = dfs(node.left, to_delete)
                node.right = dfs(node.right, to_delete)
                
                return None if to_delete else node
                            
            dfs(root, True)
            
            return res
    
    
  • /**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    func delNodes(root *TreeNode, to_delete []int) []*TreeNode {
    	s := map[int]bool{}
    	for _, v := range to_delete {
    		s[v] = true
    	}
    	ans := []*TreeNode{}
    	if !s[root.Val] {
    		ans = append(ans, root)
    	}
    	var fa *TreeNode
    	var dfs func(fa, root *TreeNode)
    	dfs = func(fa, root *TreeNode) {
    		if root == nil {
    			return
    		}
    		dfs(root, root.Left)
    		dfs(root, root.Right)
    		if s[root.Val] {
    			if fa != nil && fa.Left == root {
    				fa.Left = nil
    			}
    			if fa != nil && fa.Right == root {
    				fa.Right = nil
    			}
    			if root.Left != nil {
    				ans = append(ans, root.Left)
    			}
    			if root.Right != nil {
    				ans = append(ans, root.Right)
    			}
    		}
    	}
    	dfs(fa, root)
    	return ans
    }
    
  • /**
     * Definition for a binary tree node.
     * class TreeNode {
     *     val: number
     *     left: TreeNode | null
     *     right: TreeNode | null
     *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
     *         this.val = (val===undefined ? 0 : val)
     *         this.left = (left===undefined ? null : left)
     *         this.right = (right===undefined ? null : right)
     *     }
     * }
     */
    
    function delNodes(
        root: TreeNode | null,
        to_delete: number[],
    ): Array<TreeNode | null> {
        const s: boolean[] = Array(1001).fill(false);
        for (const x of to_delete) {
            s[x] = true;
        }
        const ans: Array<TreeNode | null> = [];
        const dfs = (root: TreeNode | null): TreeNode | null => {
            if (!root) {
                return null;
            }
            root.left = dfs(root.left);
            root.right = dfs(root.right);
            if (!s[root.val]) {
                return root;
            }
            if (root.left) {
                ans.push(root.left);
            }
            if (root.right) {
                ans.push(root.right);
            }
            return null;
        };
        if (dfs(root)) {
            ans.push(root);
        }
        return ans;
    }
    
    

All Problems

All Solutions