2021-04-11：判断二叉树是否是完全二叉树？

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

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

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

执行结果如下：