2022-03-08：给定一棵树的头节点head，
请按照题意，保留节点，没有保留的节点删掉。
树调整完之后，返回头节点。
答案2022-03-08：
递归。当前节点描黑或者子节点描黑，那就保留；否则不保留。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
n1 := NewNode(1, false)
n2 := NewNode(2, true)
n3 := NewNode(3, false)
n4 := NewNode(4, false)
n5 := NewNode(5, false)
n6 := NewNode(6, true)
n7 := NewNode(7, true)
n8 := NewNode(8, false)
n9 := NewNode(9, false)
n10 := NewNode(10, false)
n11 := NewNode(11, false)
n12 := NewNode(12, false)
n13 := NewNode(13, true)
n1.nexts = append(n1.nexts, n2)
n1.nexts = append(n1.nexts, n3)
n2.nexts = append(n2.nexts, n4)
n2.nexts = append(n2.nexts, n5)
n3.nexts = append(n3.nexts, n6)
n3.nexts = append(n3.nexts, n7)
n6.nexts = append(n6.nexts, n8)
n6.nexts = append(n6.nexts, n9)
n6.nexts = append(n6.nexts, n10)
n7.nexts = append(n7.nexts, n11)
n7.nexts = append(n7.nexts, n12)
n9.nexts = append(n9.nexts, n13)
head := retain(n1)
preOrderPrint(head)
}
type Node struct {
// 值
value int
// 是否保留
retain bool
// 下级节点
nexts []*Node
}
func NewNode(v int, r bool) *Node {
ans := &Node{}
ans.value = v
ans.retain = r
ans.nexts = make([]*Node, 0)
return ans
}
// 给定一棵树的头节点head
// 请按照题意，保留节点，没有保留的节点删掉
// 树调整完之后，返回头节点
func retain(x *Node) *Node {
if len(x.nexts) == 0 {
if x.retain {
return x
} else {
return nil
}
}
// x下层有节点
newNexts := make([]*Node, 0)
for _, next := range x.nexts {
newNext := retain(next)
if newNext != nil {
newNexts = append(newNexts, newNext)
}
}
// x.nexts 老的链表，下级节点
// newNexts 新的链表，只有保留的在里面
//
if len(newNexts) > 0 || x.retain {
x.nexts = newNexts
return x
}
return nil
}
// 先序打印
func preOrderPrint(head *Node) {
fmt.Println(head.value)
for _, next := range head.nexts {
preOrderPrint(next)
}
}
执行结果如下：
左神java代码
