Delete Nodes And Return Forest

MediumArrayHash TableTreeDepth-First SearchBinary Tree

Solution

import { TreeNode } from '@algorithm/lib';
 
export function delNodes(root: TreeNode | null, toDelete: number[]): TreeNode[] {
  const answer: TreeNode[] = [];
  const deletedNodes = new Set(toDelete);
 
  function deleteNode(node: TreeNode | null, isRootNode: boolean) {
    if (node === null) {
      return null;
    }
    const isDeleted = deletedNodes.has(node.val);
    if (isRootNode && !isDeleted) {
      answer.push(node);
    }
    node.left = deleteNode(node.left, isDeleted);
    node.right = deleteNode(node.right, isDeleted);
    return isDeleted ? null : node;
  }
  deleteNode(root, true);
 
  return answer;
}

Compelexity

  • Time: O(N)
  • Space: O(N)