2021-04-14:判断二叉树是否是满二叉树?

举报
福大大架构师每日一题 发表于 2021/04/14 22:41:55 2021/04/14
【摘要】 2021-04-14:判断二叉树是否是满二叉树?福大大 答案2021-04-14:网上查到的答案,一般会计算树的高度。我的答案不需要计算树的高度,至于是否准确,不得而知。1.左子节点满。2.右子节点满。3.左右子节点的数量相等。采用递归即可。代码用golang编写。代码如下:package mainimport "fmt"func main() { head := &TreeNode{...

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

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。