LeetCode958 二叉树的完全性检验

题目

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

在一个 完全二叉树 中，除了最后一个关卡外，所有关卡都是完全被填满的，并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2? 节点之间的最后一级 h 。

 示例 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 

方法

深度优先计数法

下标为i的节点的左子节点下标为i*2，右子节点下标为i*2+1
如果是完全二叉树，节点的个数一定等于最右下角的节点下标

• 时间复杂度：O(n)，n为节点数
• 空间复杂度：O(n)

class Solution {
    private int size= 0;
    private int maxIndex = 0;
    public boolean isCompleteTree(TreeNode root) {
        if(root==null) return true;
        dfs(root,1);
        return size==maxIndex;
    }
    private void dfs(TreeNode root,int index){
        if(root==null) return;
        size++;
        maxIndex = Math.max(maxIndex,index);
        dfs(root.left,index*2);
        dfs(root.right,index*2+1);
    }
}

广度优先计数法

• 时间复杂度：O(n)，n为节点数
• 空间复杂度：O(n)