2021-04-14：判断二叉树是否是满二叉树？

福大大架构师每日一题 · · 472 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

福大大答案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}

}

执行结果如下：