每日一题:LeetCode-958. 二叉树的完全性检验
刷题使我快乐,满脸开心.jpg
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/check-completeness-of-a-binary-tree/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题目
给你一棵二叉树的根节点 root
,请你判断这棵树是否是一棵 完全二叉树
。
在一棵 完全二叉树
中,除了最后一层外,所有层都被完全填满,并且最后一层中的所有节点都尽可能靠左。最后一层(第 h
层)中可以包含 1
到 2h
个节点。
示例 1:
复制代码
示例 2:
复制代码
提示:
树中节点数目在范围
[1, 100]
内1 <= Node.val <= 1000
思路
这个题目其实挺简单的,别被它唬住就好
完全二叉树
除最后一层必须完全填满
最后一层即使不满,也需要保证空隙的右边再没有节点
翻译成思路逻辑:
出现空隙后,不能再有下一层节点
出现空隙后,不能再有右边的节点
所以我直接选择了BFS
,很适合实现这个思路逻辑
具体不用多说了,直接上代码,细节在注释
代码
复制代码
欢迎关注公众号交流更多题目~
版权声明: 本文为 InfoQ 作者【半亩房顶】的原创文章。
原文链接:【http://xie.infoq.cn/article/ca0285effabdc5fd8d73b23cb】。文章转载请联系作者。
评论