Open tradyau opened 3 years ago
/**
* @param {TreeNode} root
* @param {number[]} to_delete
* @return {TreeNode[]}
*/
var delNodes = function (root, to_delete) {
var treeList = [root]
var stack = [root]
var node
var parentMap = {}
var delNum
var parent
// 深度优先遍历树
while (stack.length) {
node = stack.pop()
if (!node) continue
const { left, right } = node
// 记录所有节点的父节点
if (left) {
parentMap[left.val] = node
stack.push(left)
}
if (right) {
parentMap[right.val] = node
stack.push(right)
}
}
// 删除所有点
for (delNum of to_delete) {
parent = parentMap[delNum]
if (parent) {
// 要被删除的节点有父节点,说明是树的子节点
const { left } = parent
// 从父节点中删除当前节点
if (left && left.val === delNum) {
node = parent.left
parent.left = null
} else {
node = parent.right
parent.right = null
}
// 将当前节点的左右子树放到森林中
if (node.left) {
treeList.push(node.left)
delete parentMap[node.left.val]
}
if (node.right) {
treeList.push(node.right)
delete parentMap[node.right.val]
}
} else {
// 要删除的是根节点
for (var i = 0; i < treeList.length; i++) {
const { left, right, val } = treeList[i]
if (val === delNum) {
// 从森林中删除当前节点
treeList.splice(i, 1)
// 将左右子树放到深林中
if (left) {
treeList.push(left)
delete parentMap[left.val]
}
if (right) {
treeList.push(right)
delete parentMap[right.val]
}
break
}
}
}
}
return treeList
}
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number[]} to_delete
* @return {TreeNode[]}
*/
var delNodes = function(root, to_delete) {
let r = [];
let dels = new Set(to_delete);
function helper(root) {
if (root === null) {
return null;
}
if (root.left === root.right) {
if (dels.has(root.val)) {
return null;
}
return root;
}
let left = helper(root.left);
let right = helper(root.right);
if (dels.has(root.val)) {
left && r.push(left);
right && r.push(right);
return null;
}
root.left = left;
root.right = right;
return root;
}
let tree = helper(root)
tree && r.push(tree);
return r;
};
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number[]} to_delete
* @return {TreeNode[]}
*/
var delNodes = function(root, to_delete) {
const result = []
const needDelete = new Set(to_delete)
if(!needDelete.has(root.val)){
result.push(root);
}
function foreach(node, needDelete, parent) {
if (!node) return
if (needDelete.has(node.val)) {
node.left && !needDelete.has(node.left.val) && result.push(node.left)
node.right && !needDelete.has(node.right.val) && result.push(node.right)
}
node.left && foreach(node.left, needDelete, node)
node.right && foreach(node.right, needDelete, node)
if (needDelete.has(node.val)) {
node === parent.left ? parent.left = null : parent.right = null
}
}
foreach(root, needDelete, { left: root })
return result
};
https://leetcode-cn.com/problems/delete-nodes-and-return-forest/