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代码