首页 > 试题广场 >

判断是不是完全二叉树

[编程题]判断是不是完全二叉树
  • 热度指数：64362 时间限制：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，点此查看相关信息
算法知识视频讲解
添加回答
Python3
牛客782212540号头像 牛客782212540号 
class Solution:
    def isCompleteTree(self , root: TreeNode) -> bool:
        if root.left == root.right and root.left == None:
            return True
        tree = [None] * 100
        stack = [(root,0)]
        while len(stack)>0:
            cur,i = stack.pop()
            if not cur.left is None:
                stack.append((cur.left,(i<<1)+1))
            elif not cur.right is None: # 左空右值必错
                return False
            if not cur.right is None:
                stack.append((cur.right,(i<<1)+2))
            if i < 100 and cur.val != "#":
                tree[i] = 1
        for i in range(1,99):
            if tree[i] is None and not tree[i+1] is None:
                return False
        return True
想起了数组树
编辑于 2024-03-25 21:13:56 回复(0)
Python3
可道非常道头像 可道非常道 
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return bool布尔型
#
class Solution:
    def isCompleteTree(self , root: TreeNode) -> bool:
        # write code here
        if root is None:
            return True
        
        queue = [root]
        is_missing_child = False
        
        while len(queue) > 0:
            node = queue.pop(0)
            
            # 针对缺失节点的情况进行判断
            if node is None:
                is_missing_child = True
                continue
            elif is_missing_child:
                return False
            
            # 将左右子节点加入队列
            queue.append(node.left)
            queue.append(node.right)
        
        return True

发表于 2023-10-16 17:23:01 回复(0)
Python3
牛客429226965号头像 牛客429226965号
class Solution:
    def isCompleteTree(self , root: TreeNode) -> bool:
        # write code here
        NULL = '#'
        que = []
        que.append(root)
        while len(que) != 0 or root != None:
            root = que.pop(0)
            if root == NULL:
                while len(que) != 0:
                    root = que.pop()
                    if root != NULL:
                        return False
                break
            if root.left != None:
                que.append(root.left)
            else:
                que.append(NULL)
            if root.right != None:
                que.append(root.right)
            else:
                que.append(NULL)
        return True
发表于 2023-08-14 10:31:04 回复(0)
Python3
牛客292060878号头像 牛客292060878号 
class Solution:
    def isCompleteTree(self , root: TreeNode) -> bool:
        # write code here
        Tree = [root]
        flag = 0
        while Tree:
            temp = Tree.pop(0)
            if flag == 1 and temp != '#':
                return False
            if temp == '#':
                flag = 1
            else:
                if temp.left:
                    Tree.append(temp.left)
                else:
                    Tree.append('#')
                if temp.right:
                    Tree.append(temp.right)
                else:
                    Tree.append('#')
        return True
简单易懂，自己食用！
发表于 2022-10-19 14:17:31 回复(0)
Python3
牛客1217718号头像 牛客1217718号
class Solution:
    def isCompleteTree(self , root: TreeNode) -> bool:
        if not root:
            return True
        tree_nodes = [root]
        has_none = False
        while tree_nodes:
            tmp = []
            for tree_node in tree_nodes:
                if tree_node:
                    tmp.append(tree_node.left)
                    tmp.append(tree_node.right)
                    if has_none:
                        return False
                else:
                    has_none = True
            tree_nodes = tmp
        return True
发表于 2022-10-03 20:38:23 回复(0)
Python3
JianYue头像 JianYue 
class Solution:
    def isCompleteTree(self , root: TreeNode) -> bool:
        if root is None:
            return True
        ret = [root]
        while ret:
            cur = ret.pop(0)
            if cur:
                ret.append(cur.left)
                ret.append(cur.right)
            else:
                break
        for i in ret:
            if i:
                return False
        return True

发表于 2022-09-17 18:04:15 回复(0)
Python3
TTThanos头像 TTThanos 
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return bool布尔型
#
class Solution:
    def isCompleteTree(self , root: TreeNode) -> bool:
        if not root:
            return True
        queue = [root]
        flag = False
        while queue:
            node = queue.pop()
#           第一次碰到空节点，改一下标记
            if not node:
                flag = True
            else:
#                 若该节点不空而且之前出现了空节点，则证明不是完全二叉树
                if flag and len(queue) > 0:
                    return False
                queue.insert(0, node.left)
                queue.insert(0, node.right)
        return True
                
            
                
        
        

发表于 2022-06-21 23:45:56 回复(0)
Python3
牛客788327651号头像 牛客788327651号 
class Solution:
    def isCompleteTree(self , root: TreeNode) -> bool:
        # write code here
        alist = [root]
        isLeaf = False
        while alist and not isLeaf:
            node = alist.pop()
            if not node:
                isLeaf = True
            else:
                alist.insert(0, node.left)
                alist.insert(0, node.right)
        complete = True
        for i in alist:
            if i:
                complete = False
                break
        return complete

发表于 2022-05-24 10:12:41 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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