题目

题目来源：力扣（LeetCode）

给出二叉树的根节点 root，树上每个节点都有一个不同的值。

如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。

返回森林中的每棵树。你可以按任意顺序组织答案。

示例：
image.png
输入：root = [1,2,3,4,5,6,7], to_delete = [3,5]
输出：[[1,2,null,4],[6],[7]]

思路分析

使用前序遍历递归遍历各个节点，然后判断节点值是否是需要删除的值，如果是，就将该节点删除，然后判断子节点是否为要删除的值，如果不是则将子节点加入结果集中。

具体地：

  1. 首先判断根节点是否是需要删除的值，如果不是，则将根节点加入结果集中
  2. 然后递归遍历所有节点，判断当前节点是否是需要删除的值：
  3. 如果是，则需要将该节点的 不是要删除的子节点 加入结果集中
  4. 递归处理左子树和右子树
  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @param {number[]} to_delete
  12.  * @return {TreeNode[]}
  13.  */
  14. var delNodes = function (root, to_delete) {
  15.   let result = [];
  16.   // 使用 set 集合存储需要删除节点值，便于快速找到需要删除的节点
  17.   let needDelete = new Set(to_delete);
  18.   // 首先判断根节点是否需要删除，如果不需要删除，则将其加入结果集中
  19.   if (!needDelete.has(root.val)) {
  20.     result.push(root);
  21.   }
  22.   tools(root, needDelete, { left: root });
  23.   return result;
  25.   function tools(node, needDelete, p) {
  26.     // 递归退出条件
  27.     if (!node) return;
  28.     // 判断当前节点是否需要删除，如果当前节点需要删除，则需要判断是否有孩子节点
  29.     if (needDelete.has(node.val)) {
  30.       // 有左子节点并且左子节点不需要删除，则将当前节点的左子树加入结果集
  31.       node.left && !needDelete.has(node.left.val) && result.push(node.left)
  32.       // 有右子节点并且右子节点不需要删除，则将当前节点的右子树加入结果集
  33.       node.right && !needDelete.has(node.right.val) && result.push(node.right);
  34.     }
  36.     // 递归左右子树
  37.     node.left && tools(node.left, needDelete, node);
  38.     node.right && tools(node.right, needDelete, node);
  40.     // 当前删除的节点是某个父节点的节点，则需要将该父节点的左子节点或右子节点置为 null
  41.     if (needDelete.has(node.val)) {
  42.       node === p.left ? p.left = null : p.right = null;
  43.     }
  44.   }
  45. };