昨天的
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
}