昨天的
1110. Delete Nodes And Return Forest
给一个二元树
和一个to_delete矩阵
请把所有在to_delete中的节点删掉
并且回传所有剩下的树
思路:
就照做
用dfs
先把左右子节点丢到dfs里
接着判断node是不是要删除的
(1)要:
就把经过dfs处理回传后的左右子节点(如果不是NULL)记录到result，并回传NULL
(2)不用:
就回传null
最后再判断一下ROOT要不要删掉就好
GOLANG CODE
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func delNodes(root *TreeNode, to_delete []int) []*TreeNode {
todelete := make(map[int]struct{})
for _, val := range to_delete {
todelete[val] = struct{}{}
}
res := []*TreeNode{}
var dfs func(*TreeNode) *TreeNode
dfs = func(node *TreeNode) *TreeNode {
if node == nil {
return nil
}
l := dfs(node.Left)
r := dfs(node.Right)
if _, ok := todelete[node.Val]; ok {
if l != nil {
res = append(res, l)
}
if r != nil {
res = append(res, r)
}
return nil
} else {
node.Left = l
node.Right = r
return node
}
}
dfs(root)
if _, ok := todelete[root.Val]; !ok {
res = append(res, root)
}
return res
}