题目主要信息

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

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

方法一：层次遍历

具体方法

使用层次遍历，每一层从左到右遍历节点。

由于判断完全二叉树，当遍历当前层时如果遇到空节点，如果该空节点右侧还有节点，说明该树一定不是完全二叉树，直接返回false，遍历完返回true；

代码实现

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    public boolean isCompleteTree (TreeNode root) {
        // write code here
        //标记空节点
        boolean left =  true;
        if(root == null) 
              return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode nowNode = queue.poll();
            //说明当前节点是空节点
            if(nowNode == null){
                left = false;
            }else{
                // 遇到空节点直接返回false
                if(left == false)
                    return false;
                queue.offer(nowNode.left);
                queue.offer(nowNode.right);
            }
        }
        return true;
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，所有节点都需要遍历
• 空间复杂度：$O(n)O(n)$，队列最多存储n/2个节点

方法二：深度优先搜索

具体方法

本题是需要判断完全二叉树，而完全二叉树有下面公式，如果某个节点索引是i，那么他的左右子节点为（索引从1开始）

$left=2\ast ileft\; =\; 2*i$

$right=2\ast i+1right\; =\; 2*i+1$

两个计数操作

• 计数当前遍历访问的节点是第几个节点
• 计数在完全二叉树中，当前访问的节点在完全二叉树中的编号

如果最终得到的两个值相同，说明该树是一棵完全二叉树

如果最终得到的两个值不同，说明该树不是一棵完全二叉树

代码实现

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    int ans = 0;
    int dfs(TreeNode root, int idx){
        if(root == null) return 0;
        ans = Math.max(ans, idx);
      //遍历左右子树
        return 1 + dfs(root.left, idx * 2) + dfs(root.right, idx * 2 + 1);
    }
    public boolean isCompleteTree (TreeNode root) {
      // dfs判断节点的序号是否等于编号
        return dfs(root, 1) == ans;
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，需要遍历所有的节点
• 空间复杂度：$O(n)O(n)$。在平均情况下，二叉树的高度与节点个数为对数关系，即$O(logn)O(log\; n)$。而在最坏情况下，树形成链状，空间复杂度为 $O(n)O(n)$。