/*
* @lc app=leetcode.cn id=1110 lang=typescript
*
* [1110] 删点成林
*/
// @lc code=start
/**
* 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> {}
// @lc code=end
function delNodes(root: TreeNode | null, to_delete: number[]): Array<TreeNode | null> {
if (!root) return []
const res: Array<TreeNode | null> = [],
set = new Set(to_delete)
const dfs = (node: TreeNode | null) => {
if (!node) return true
const ans = set.has(node.val)
for (let child of ['left', 'right']) {
if (!node[child]) continue
if (dfs(node[child])) {
node[child] = null
} else {
if (ans) res.push(node[child])
}
}
return ans
}
if (!dfs(root)) res.push(root)
return res
}
test.each([
{ input: { root: [1, 2, 3, 4, 5, 6, 7], to_delete: [3, 5] }, output: [[1, 2, null, 4], [6], [7]] },
{ input: { root: [1, 2, 4, null, 3], to_delete: [3] }, output: [[1, 2, 4]] },
])('input: root = $input.root, to_delete = $input.to_delete', ({ input: { root, to_delete }, output }) => {
expect(delNodes(BinaryTree.deserialize(root), to_delete).sort((a, b) => a!.val - b!.val)).toEqual(
output.map(BinaryTree.deserialize).sort((a, b) => a!.val - b!.val),
)
})