958. 二叉树的完全性检验

题目描述

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

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

输入输出

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

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

基本思路

一颗二叉树是完全二叉树当且仅当节点编号依次为 1, 2, 3, …n 且没有间隙。换句话说，可以将其表示为一个值为1~n的连续数组。而在一个值从1开始的连续数组中，数组中最大元素值等于数组大小。 在根节点编号值为1的完全二叉树则是，节点编号最大值等于节点个数。

  • 从根节点开始搜索，并将根节点编号值设置为1。
  • 然后搜索左子树，并传递其根节点值为2k。搜索右子树，并传递其根节点值为2*k+1
  • 在递归搜索过程中，记录节点个数size和当前最大节点编号值max。
  • 最后判断最大节点值max和节点数size是否相等，相等则该二叉树是完全二叉树，否则不是。

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    int size = 0;//实际节点数
    int max = 0;//当前最大节点编号值
    public boolean isCompleteTree(TreeNode root) {
        if(root == null) return true;
        recur(root, 1);
        return size == max;
    }

    public void recur(TreeNode root, int index) {
        if(root == null) return;
        size++;
        max = Math.max(max, index);
        recur(root.left, index * 2);
        recur(root.right, index * 2 + 1);
    }
}