image.png

思路1：利用下标进行计数

  • 用BFS数组来存储完全二叉树，如果数组大小和数组中最后一个元素的下标相同，那么就是完全二叉树，反之必然不是。
  • 每个元素都有一个自己的编号，代表它是层序遍历中第index个访问到的元素
  • 编号LC958.二叉树的完全性检验 - 图2的节点，其左孩子的编号为LC958.二叉树的完全性检验 - 图3，右孩子编号 LC958.二叉树的完全性检验 - 图4（编号从0开始）
  • 通过node_seq.size() - 1 == 最后一个元素的下标判断是不是完全二叉树
  • 无论什么情况下，假设层数为LC958.二叉树的完全性检验 - 图5，最后一个元素的下标必然是LC958.二叉树的完全性检验 - 图6（因为下标从0开始，实际上就是如果此树是完全二叉树，LC958.二叉树的完全性检验 - 图7）
  • 此题提供了利用数组方式BFS的一种思路，常见的队列方式也可以做，大部分BFS问题两种方法都可以换着来。

image.png

代码1：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     bool isCompleteTree(TreeNode* root) {
  15.         // 利用标记进行BFS
  16.         vector<pair<TreeNode* ,int>> node_seq;
  17.         node_seq.push_back({root, 0});
  19.         // queue的大小不断变化
  20.         for (int i = 0; i < node_seq.size(); ++i) {
  21.             pair<TreeNode*, int> cur_pos;
  22.             cur_pos.first = node_seq[i].first;
  23.             cur_pos.second = i;
  25.             if (cur_pos.first->left) {node_seq.push_back({cur_pos.first->left, 2 * i + 1});}
  26.             if (cur_pos.first->right) {node_seq.push_back({cur_pos.first->right, 2 * i + 2});}
  27.         }
  29.         // 因为是从0开始的
  30.         return node_seq.size() - 1 == node_seq[node_seq.size() - 1].second;
  31.     }
  32. };

思路2：主流做法，判断之前是否出现过空节点

  • 设置一个have_nullptr判断是不是出现过空节点
  • 如果出现过空节点之后，仍然会出现非空节点，立即返回false
  • 可以通过常规的队列去做，这里采用了按照下标构建数组的方式，大部分BFS问题，两种2方式都可以换着使用

    代码2：

  1. class Solution {
  2. public:
  3.     bool isCompleteTree(TreeNode* root) {
  4.         vector<pair<TreeNode*, int>> nodes;
  5.         nodes.push_back({root, 0});
  7.         bool have_nullptr = false;
  8.         for (int i = 0; i < nodes.size(); i++) {
  9.             pair<TreeNode*, int> cur_node = nodes[i];
  11.             if (cur_node.first->left) {
  12.                 if (have_nullptr) return false;
  13.                 nodes.push_back({cur_node.first->left, 2 * i + 1});
  14.             } else {
  15.                 have_nullptr = true;
  16.             }
  18.             if (cur_node.first->right) {
  19.                 if (have_nullptr) return false;
  20.                 nodes.push_back({cur_node.first->right, 2 * i + 2});
  21.             } else {
  22.                 have_nullptr = true;
  23.             }
  24.         }
  26.         return true;
  27.     }
  28. };