作者JIWP (神楽めあ的錢包)
標題Re: [閒聊] 每日leetcode
時間2024-07-18 23:48:00
昨天的
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
}
--
※ 發信站: 批踢踢實業坊(ptt-website.tw), 來自: 111.71.212.132 (臺灣)
※ 文章網址: https://ptt-website.tw/Marginalman/M.1721317683.A.0CC
推 sixB: 大師 07/18 23:52
→ oin1104: 我好崇拜你 07/18 23:54
→ DJYOMIYAHINA: 我好崇拜你 07/18 23:56