Leetcode958. 二叉树的完全性检验

2021年5月29日 219点热度 1人点赞 0条评论

题目描述

给定一个二叉树,确定它是否是一个完全二叉树

百度百科中对完全二叉树的定义如下:

若设二叉树的深度为 h,除第 h 层外,其它各层 ($1 \quad to \quad h-1$) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。(注:第 h 层可能包含 $1 \quad to \quad 2^h$ 个节点。)

示例 1:

img

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

示例 2:

img

输入:[1,2,3,4,5,null,7]
输出:false
解释:值为 7 的结点没有尽可能靠向左侧。

提示:

  1. 树中将会有 1 到 100 个结点。

解题思路

关于完全二叉树的定义还是比较熟悉的,但是乍一看到这道题有点懵。官方题解的方法是重新同一个code变量给每一个结点标记,规则为:父节点为i的话,左孩子为2i,右孩子为2i+1。其实的根节点标记为1。最后看最右端结点的code值是不是结点的数量。这个方法当然是可行的,但是有点繁琐。

有一个更加巧妙的方法。完全二叉树如果用广度优先搜索的方法,也就是层序遍历的话,当出现一个空节点的时候,后续就不能再出现非空结点。反过来说,如果在层序遍历的过程中,在出现空节点后又出现了非空结点,那么这个二叉树一定不是完全二叉树

据此可以写出对应的代码:

bool isCompleteTree(TreeNode* root)
{
    if(root==nullptr) return true;
    queue<TreeNode*>q;
    bool isNullptr=false;
    q.push(root);
    while(!q.empty())
    {
        TreeNode* cur=q.front();
        q.pop();
        if(cur==nullptr)
        {
            isNullptr=true;
            continue;
        }
        else{
            if(isNullptr)
            {
                //在空节点后又出现非空结点
                return false;
            }
            q.push(cur->left);
            q.push(cur->right);
        }
    }
    return true;
}

时间复杂度为:$O(n)$,$n$为二叉树的结点个数

空间复杂度为:$O(n)$,$n$为二叉树的结点个数

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论