BM35. [判断是不是完全二叉树]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM35. 判断是不是完全二叉树

https://www.nowcoder.com/practice/8daa4dff9e36409abba2adbe413d6fae?tpId=295&sfm=github&channel=nowcoder

题目分析

首先我们需要知道什么是完全二叉树，叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

这里面最重要的一句话就是叶子结点只能出现在最下层和次下层，所以我们想到可以使用层序遍历，只有次下层和最下层才有叶子节点。想一下我们对称的二叉树层序回文求解过程，将每层的空节点也填充了进去。

具体做法
所以层序遍历过程次下层会出现一个空节点，然后接续向后遍历，且在遍历结束之前也就是queue不为空之前不会再出现空节点，如果出现就不是完全二叉树

代码如下

while(!queue.isEmpty()){
  TreeNode cur = queue.pop();
  cur在这个里面仅仅只能有一次为空,否则就不是完全二叉树
}

转化为代码直接使用层序遍历模板

public boolean isCompleteTree (TreeNode root) {
  //如果是空节点就是true
        if(root==null){
        return true;
    }
    Queue<TreeNode> queue=new LinkedList<>();
    queue.offer(root);
    TreeNode cur;
    //定义一个首次出现的标记位
    boolean notComplete=false;
    while (!queue.isEmpty()){
        cur=queue.poll()();
        if(cur==null){
            notComplete=true;
            //第一个空节点之后的节点，countinue使用的很妙
            continue;
        }
        if(notComplete){
            return false;
        }
        queue.offer(cur.left);
        queue.offer(cur.right);
    }
    return true;
}

复杂度分析：

• 时间复杂度：O(n)，无论中序遍历、层次遍历还是检查排序都是O(n)
• 空间复杂度：O(n)，中序递归最大栈空间和层次队列的最大空间都为O(n)