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;
}

1110 - Delete Nodes And Return Forest

1110. Delete Nodes And Return Forest (Medium)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

1110. Delete Nodes And Return Forest (Medium)

Solution 1.

All Problems

All Solutions