二叉树 - 二叉树的完全性检验 - 《数据结构与算法》

题目
思路分析
- 深度优先搜索
- 广度优先搜索

题目

题目来源：力扣（LeetCode）

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

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

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

示例 1：

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

示例 2：

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

思路分析

深度优先搜索

总体思路

对二叉树的节点进行编号，并统计节点的个数，判断节点编号最大值是否等于节点个数，若等于，便是完全二叉树。

具体分析

在完全二叉树中，用 1 表示根节点编号，则对于任意一个节点 x，它的左孩子为 2x，右孩子为 2x + 1 。那么我们可以发现，一颗二叉树是完全二叉树当且仅当节点编号依次为 1, 2, 3, …n 且没有间隙。换句话说，可以将其表示为一个值为1~n的连续数组。而在一个值从1开始的连续数组中，数组中最大元素值等于数组大小。 在根节点编号值为1的完全二叉树则是，节点编号最大值等于节点个数。

搜索过程如下：

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

递归边界：

1、递归到叶子节点，子树递归结束，返回true。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
// 在完全二叉树中，用 1 表示根节点编号，则对于任意一个节点 x，它的左孩子为 2*x，右孩子为 2*x + 1
var isCompleteTree = function(root) {
  let count = 0;  // 统计节点个数
  let maxNum = 0; // 记录最大节点编号值
  dfs(root,1);
  // 递归结束后 count 和 maxNum都收集完毕才能根据 count和maxNum来判断
  // 判断最大节点值是否和节点数相等
  return count === maxNum 
  function dfs (root, index) {
    if (root == null) return;  // 递归到了叶子节点
    count++; // 统计节点树
    maxNum = Math.max(maxNum, index); // 记录最大节点编号值
    // 递归左右子树
    dfs(root.left, 2 * index)
    dfs(root.right, 2 * index + 1)  
  }
};

广度优先搜索

BFS + 判断空节点后面是否还有非空节点

对于完全二叉树，层序遍历的过程中遇到第一个空节点之后不应该再出现非空节点，否则就不是完全二叉树。

定义 queue 队列存放节点，定义 isNull 记录第一次遇到空节点的情况。

首先将根节点放入队列中，遍历队列，在遍历的过程中，如果已经出现一个空节点后，又出现一个非空节点，说明为非完全二叉树。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
// 对于一个完全二叉树，层序遍历的过程中遇到第一个空节点之后不应该再出现非空节点
var isCompleteTree = function(root) {
  let isNull = false; // 定义 isNull 记录第一次遇到空节点的情况
  const queue = [root];
  while(queue.length) {
    const node = queue.shift();
    // 如果已经出现一个空节点后，有出现非空节点，说明为非完全二叉树
    if (isNull && node) return false;
    // 节点不为空，左右孩子入队
    if (node) {
      queue.push(node.left);
      queue.push(node.right);
    } else {
      isNull = true;
    }
  }
  return true;
};

BFS + 判断当前节点编号值与当前统计节点数量是否相等

完全二叉树可以用数组表示。我们将一个值为1~n的连续数组表示成一个完全二叉树如下图所示：

在层序遍历的过程中，如果当前节点编号值与当前统计的节点个数不一致，说明该二叉树不是完全二叉树。

层序遍历过程如下：

1、我们从根节点开始搜索，并将根节点编号值设置为1。
2、然后搜索左子树，并传递其根节点值为2k。搜索右子树，并传递其根节点值为2k+1
3、在层序遍历过程中，记录节点个数 count
4、最后判断当前节点编号值与当前统计的节点个数是否相等，相等则该二叉树是完全二叉树，否则不是。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isCompleteTree = function(root) {
  if (!root) {
    return true
  }
  const queue = [{ node: root, index: 1 }]
  let count = 0
  while (queue.length) {
    const temp = queue.shift()
    const node = temp.node
    const index = temp.index
    // 完全二叉树可以使用数组表示，我们将一个值为 1 ~ n 的连续数组表示成一个完全二叉树
    // 如果是完全二叉树，当前节点编号值与当前统计的节点数量是相等的，如若不等，说明不是一个完全二叉树
    if (index !== ++count) {
        return false
    }
    // 层序遍历过程中，用index来维护节点索引，如果根节点index为1，那么一个节点索引是index,
    // 那他的左孩子索引是index * 2,右孩子索引是index * 2 +1
    node.left && queue.push({ node: node.left, index: index * 2 })
    node.right && queue.push({ node: node.right, index: index * 2 + 1 })
  }
  return true
};