首页 > 试题广场 >

判断是不是完全二叉树

[编程题]判断是不是完全二叉树
  • 热度指数：64418 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个二叉树，确定他是否是一个完全二叉树。

完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 [1~2h] 个节点）

数据范围：节点数满足
样例图1：
样例图2：
样例图3：

示例1

输入

{1,2,3,4,5,6}

输出

true
示例2

输入

{1,2,3,4,5,6,7}

输出

true
示例3

输入

{1,2,3,4,5,#,6}

输出

false

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Go
hzmg头像 hzmg
思路：完全二叉树需要满足以下几个条件：
当该行不完整时，需确保：
1.该行中每个节点都没有子节点
2.不能出现有左节点没有右节点的情况
3.若该行中已有空节点则后续不能存在任何节点
然后根据这三条使用广度优先遍历，并按顺序判断即可。
代码： 
func isCompleteTree(root *TreeNode) bool {
	var queue = list.New()
	var count = 0
	queue.PushBack(root)
	for queue.Len() != 0 {
		size := queue.Len()
		count++
		mayCount := int(math.Pow(float64(2), float64(count-1)))
		var isComplete = true
		for i := 0; i < size; i++ {
			node := queue.Front().Value.(*TreeNode)
			queue.Remove(queue.Front())

			if size != mayCount && (node.Left != nil || node.Right != nil) {
				return false
			}
			if node.Right != nil && node.Left == nil {
				return false
			}
			if (node.Left != nil || node.Right != nil) && isComplete == false {
				return false
			}
			if node.Left == nil || node.Right == nil {
				isComplete = false
			}

			if node.Left != nil {
				queue.PushBack(node.Left)
			}
			if node.Right != nil {
				queue.PushBack(node.Right)
			}
		}
	}
	return true
	// write code here
}


发表于 2022-11-15 17:32:42 回复(0)
Go
big_dreamer头像 big_dreamer

基于层次遍历判断是否为完全二叉树 

package main

import . "nc_tools"

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @return bool布尔型
 */
func isCompleteTree(root *TreeNode) bool {
	if root == nil {
		return true
	}
    
    notComplete := false
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        tempQueue := []*TreeNode{}
        for _, node := range queue {
            if node == nil {
                notComplete = true
                continue
            }
            if notComplete {
                return false // 第二次出现空节点
            }
            
            tempQueue = append(tempQueue, node.Left)
            tempQueue = append(tempQueue, node.Right)
        }
        queue = tempQueue
    }
    
    return true
}


发表于 2022-05-19 23:00:33 回复(0)
Go
丶极客先生头像 丶极客先生
检查结束的标志
1.倒数最后一层上面的节点数量分别等于2<<(n-1)，就是2的n-1次方
2.最后一层判定 如果n-1层左节点为空，右节点不为空 直接false   当最后一层节点一个为空，后面又遇到一个非空直接false，具体看代码吧


var layers [][]*TreeNode

func completeByLayer(t *TreeNode, layer int) {
    if t == nil {
        return
    }

    if len(layers) == layer {
        layers = append(layers, []*TreeNode{})
    }
    layers[layer] = append(layers[layer], t)

    completeByLayer(t.Left, layer+1)
    completeByLayer(t.Right, layer+1)
}

func isCompleteTree(root *TreeNode) bool {
    if root == nil {
        return true
    }

    completeByLayer(root, 0)
    if len(layers)==1{
        return true
    }
    for layer_index, v := range layers {

        if layer_index == len(layers)-1 {
            break
        }
        if len(v) != 1<<layer_index {
            return false
        }
    }

    status := 0
    for _, v := range layers[len(layers)-2] {
        if v.Left == nil && v.Right != nil {
            return false
        }
        //首次遇到空节点
        if status == 0 && (v.Left == nil || v.Right == nil) {
            status++
            continue
        }
        if status == 1 && (v.Left != nil || v.Right != nil) { //当有了空节点以后又遇到了非空节点 所以 *** 当然返回false
            return false
        }
    }
    return true
}

发表于 2022-03-21 11:12:47 回复(0)
提交观点

问题信息

树 dfs 广度优先搜索(BFS)
难度：
3条回答 3546浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号