2021-04-14：判斷二叉樹是否是滿二叉樹？
福大大 答案2021-04-14：
網上查到的答案，一般會計算樹的高度，我的答案不需要計算樹的高度，至于是否準確，不得而知，
1.左子節點滿，
2.右子節點滿，
3.左右子節點的數量相等，
采用遞回即可，
代碼用golang撰寫，代碼如下：
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://www.uj5u.com/qukuanlian/276246.html
標籤：區塊鏈