2021-04-11:判断二叉树是否是完全二叉树?
【摘要】 2021-04-11:判断二叉树是否是完全二叉树?福大大 答案2021-04-11:按层遍历。代码用golang编写。代码如下:package mainimport ( "container/list" "fmt")func main() { head := &TreeNode{Val: 1} head.Left = &TreeNode{Val: 2} head...
2021-04-11:判断二叉树是否是完全二叉树?
福大大 答案2021-04-11:
按层遍历。
代码用golang编写。代码如下:
package main
import (
"container/list"
"fmt"
)
func main() {
head := &TreeNode{Val: 1}
head.Left = &TreeNode{Val: 2}
head.Right = &TreeNode{Val: 3}
head.Left.Left = &TreeNode{Val: 4}
//head.Right.Right = &TreeNode{Val: 5}
ret := isCBT1(head)
fmt.Println(ret)
}
//Definition for a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func isCBT1(head *TreeNode) bool {
if head == nil {
return true
}
queue := list.New()
// 是否遇到过左右两个孩子不双全的节点
leaf := false
var l *TreeNode
var r *TreeNode
queue.PushBack(head)
for !(queue.Len() == 0) {
head = queue.Remove(queue.Front()).(*TreeNode)
l = head.Left
r = head.Right
if
// 如果遇到了不双全的节点之后,又发现当前节点不是叶节点
(leaf && (l != nil || r != nil)) || (l == nil && r != nil) {
return false
}
if l != nil {
queue.PushBack(l)
}
if r != nil {
queue.PushBack(r)
}
if l == nil || r == nil {
leaf = true
}
}
return true
}
执行结果如下:
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)