leetcode958. 二叉树的完全性检验

leetcode958. 二叉树的完全性检验

三月 14, 2020

leetcode958. 二叉树的完全性检验

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

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

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

我的思路

层序遍历,先求高度,特殊处理最后一层.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public boolean isCompleteTree(TreeNode root) {
        if(root==null)return false;
        if(root.left==null&&root.right==null)return true;
        int height=height(root);
        height--;//从第0层开始计数
        Queue<TreeNode>queue=new LinkedList<>();
        queue.offer(root);
        int level=0,count=0,flag=0;
        while(!queue.isEmpty()){
            int nowCount=1<<level;
            if(queue.size()!=nowCount)return false;
            if(level==height-1)break;
            int size=queue.size();
            for(int i=0;i<size;i++){
                TreeNode node=queue.remove();
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            level++;
        }
        //倒数第二层的情况
        for(var q:queue){
            if(flag==0){
                if(q.left==null&&q.right==null)flag=1;
                if(q.left==null&&q.right!=null)return false;
                if(q.left!=null&&q.right==null)flag=1;
                
            }else if(flag==1){
                if(q.left!=null||q.right!=null)return false;
            }
            
        }
        return true;
    }
    public int height(TreeNode root){
        if(root==null)return 0;
        int height=1;
        return Math.max(height(root.left),height(root.right))+height;
    }
}

这么想复杂,而且比较慢

解法二

在评论区看到的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    /**
     * 广度遍历二叉树，当出现 null 值时停止遍历，如果此时还有没有遍历到的结点，说明该树非完全二叉树。
     */
    public boolean isCompleteTree(TreeNode root) {
        LinkedList<TreeNode> q = new LinkedList<>();
        TreeNode cur;
        q.addLast(root);
        while ((cur = q.removeFirst()) != null) {
            q.addLast(cur.left);
            q.addLast(cur.right);
        }
        while (!q.isEmpty()) {
            if (q.removeLast() != null) {
                return false;
            }
        }
        return true;
    }
}

leetcode 53/100