写点什么

每日一题:LeetCode-958. 二叉树的完全性检验

作者:半亩房顶
  • 2024-02-01
    北京
  • 本文字数:1118 字

    阅读完需:约 4 分钟

每日一题:LeetCode-958. 二叉树的完全性检验

刷题使我快乐,满脸开心.jpg



题目

给你一棵二叉树的根节点 root ,请你判断这棵树是否是一棵 完全二叉树


在一棵 完全二叉树 中,除了最后一层外,所有层都被完全填满,并且最后一层中的所有节点都尽可能靠左。最后一层(第 h 层)中可以包含 12h 个节点。


示例 1:



输入:root = [1,2,3,4,5,6]输出:true解释:最后一层前的每一层都是满的(即,节点值为 {1} 和 {2,3} 的两层),且最后一层中的所有节点({4,5,6})尽可能靠左。
复制代码


示例 2:



输入:root = [1,2,3,4,5,null,7]输出:false解释:值为 7 的节点不满足条件「节点尽可能靠左」。
复制代码


提示:


  • 树中节点数目在范围 [1, 100]

  • 1 <= Node.val <= 1000

思路

这个题目其实挺简单的,别被它唬住就好

完全二叉树

  • 除最后一层必须完全填满

  • 最后一层即使不满,也需要保证空隙的右边再没有节点


翻译成思路逻辑:


  • 出现空隙后,不能再有下一层节点

  • 出现空隙后,不能再有右边的节点


所以我直接选择了BFS,很适合实现这个思路逻辑


具体不用多说了,直接上代码,细节在注释

代码

func isCompleteTree(root *TreeNode) bool {    // 表明是否出现空隙    notFull := false    // 选用BFS,辅助变量    nodeList := []*TreeNode{root}    temp := make([]*TreeNode, 0)    for len(nodeList) > 0 {        for _, node := range nodeList {            // 已经出现空隙了,还有下一层或者后续节点有子节点,那就不满足了            if notFull && (node.Left != nil || node.Right != nil) {                return false
// 左边有空隙,右边有子节点,那就直接可以返回false了 } else if node.Left == nil && node.Right != nil { return false
// 左右子节点都满的,加入下一层遍历节点中 } else if node.Left != nil && node.Right != nil { temp = append(temp, node.Left) temp = append(temp, node.Right)
// 右子节缺失,左子节点加入下一层遍历节点中,并且声明已经出现空隙 } else if node.Left != nil && node.Right == nil { temp = append(temp, node.Left) notFull = true
// 剩下的其实是左右子节点都为空的情况,声明出现空隙 } else { notFull = true } } nodeList = temp temp = nil } return true}
复制代码




欢迎关注公众号交流更多题目~


发布于: 刚刚阅读数: 3
用户头像

半亩房顶

关注

人生那么长,能写多少bug? 2018-11-16 加入

我希望,自己永远是自己。我希望,远离bug。

评论

发布
暂无评论
每日一题:LeetCode-958. 二叉树的完全性检验_面试_半亩房顶_InfoQ写作社区