福大大架构师每日一题

福大大架构师每日一题

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
}

执行结果如下:
2021-04-11:判断二叉树是否是完全二叉树?-LMLPHP


左神java代码
评论

04-17 01:07