2021-04-14：判断二叉树是否是满二叉树？
福大大 答案2021-04-14：
网上查到的答案，一般会计算树的高度。我的答案不需要计算树的高度，至于是否准确，不得而知。
1.左子节点满。
2.右子节点满。
3.左右子节点的数量相等。
采用递归即可。
代码用golang编写。代码如下：
```go
package main
import "fmt"
func main() {
head := &TreeNode{Val: 5}
head.Left = &TreeNode{Val: 3}
head.Right = &TreeNode{Val: 7}
head.Left.Left = &TreeNode{Val: 2}
head.Left.Right = &TreeNode{Val: 4}
head.Right.Left = &TreeNode{Val: 6}
head.Right.Right = &TreeNode{Val: 8}
ret := IsFBT(head)
fmt.Println("是否是满二叉树：", ret)
}
//Definition for a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
type Info struct {
IsFull bool
Cnt int
}
func IsFBT(head *TreeNode) bool {
return process(head).IsFull
}
func process(head *TreeNode) *Info {
if head == nil {
return &Info{IsFull: true}
}
leftInfo := process(head.Left)
//左不满
if !leftInfo.IsFull {
return leftInfo
}
rightInfo := process(head.Right)
//右不满
if !rightInfo.IsFull {
return rightInfo
}
//左右不等
if leftInfo.Cnt != rightInfo.Cnt {
return new(Info)
}
//通过所有考验
return &Info{IsFull: true, Cnt: leftInfo.Cnt + rightInfo.Cnt + 1}
}
```
执行结果如下：
***
[左神java代码](https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src/class12/Code04_IsFull.java)
[评论](https://user.qzone.qq.com/3182319461/blog/1618354692)
本文分享自微信公众号 - 福大大架构师每日一题（gh_bbe96e5def84）。
如有侵权，请联系 [email protected] 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。