![](/contact/xiaochengxu.jpg)
![](/contact/xiaohongshu.jpg)
检查给定的二叉树是否是和树
编写一个函数,如果给定的二叉树是 SumTree,则返回 true,否则返回 false。SumTree 是二叉树,其中节点的值等于其左子树和右子树中存在的节点之和。空树就是SumTree,空树的和可以认为是0。叶子节点也可以认为是SumTree。
以下是 SumTree 的示例。
26
/ \
10 3
/ \ \
4 6 3
*方法一(简单)*
获取左子树和右子树中的节点之和。检查计算的总和是否等于根的数据。另外,递归检查左子树和右子树是否是 SumTree。
package main
import (
"testing"
)
// 初始化树节点
func NewNode() *Node {
return &Node{
Data: 26,
Left: &Node{
Data: 10,
Left: &Node{
Data: 4,
Left: nil,
Right: nil,
},
Right: &Node{
Data: 6,
Left: nil,
Right: nil,
},
},
Right: &Node{
Data: 3,
Left: nil,
Right: &Node{
Data: 3,
Left: nil,
Right: nil,
},
},
}
}
// 判断是否是和树
func isSumTree(node *Node) bool {
if node != nil {
if node.Left != nil && node.Right != nil && node.Data == (node.Left.Data+node.Right.Data) {
return true
}
if node.Left != nil {
return isSumTree(node.Left)
}
if node.Right != nil {
return isSumTree(node.Right)
}
}
return false
}
func Test_isSumTree(t *testing.T) {
if isSumTree(NewNode()) {
t.Log("this is a sum tree")
} else {
t.Log("this not is a sum tree")
}
}
类似的帖子
![](/contact/xiaochengxu.jpg)
![](/contact/xiaohongshu.jpg)