958. Check Completeness of a Binary Tree

解法

这里主要还是要清楚完全二叉树的定义。从层的视角来看，所有节点都是左对齐的，并且中间不能出现空位，因为我们可以通过层序遍历来解题。

代码

  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.         if (!root) return true;
  16.         queue<TreeNode *> q;
  17.         q.push(root);
  18.         bool is_leaf = false;
  19.         while(q.size()) {
  20.             auto n = q.front();
  21.             q.pop();
  22.             // 叶子节点
  23.             if (!n->left && !n->right) {
  24.                 is_leaf = true;
  25.                 continue;
  26.             }
  27.             // 期望是叶子节点，但该节点仍然有儿子
  28.             if (is_leaf && (n->right || n->left)) {
  29.                 return false;
  30.             }
  31.             // 右儿子存在，左儿子不存在，有空缺
  32.             if (n->right && !n->left) {
  33.                 return false;
  34.             }
  35.             // 左儿子存在，右儿子不存在，有空缺，之后出现的所有节点应该是叶子节点
  36.             if (n->left && !n->right) {
  37.                 is_leaf = true;
  38.             }
  39.             if (n->left) q.push(n->left);
  40.             if (n->right) q.push(n->right);
  41.         }
  42.         return true;
  43.     }
  44. };
  • 下面这种方式更直观，把左右儿子一股脑塞进队列，如果出现了一个空位，之后必须全是空位
    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.       if (!root) return true;
    16.       queue<TreeNode *> q;
    17.       q.push(root);
    18.       bool is_leaf = false;
    19.       while(q.size()) {
    20.           auto n = q.front();
    21.           q.pop();
    22.           if (!n) {
    23.               while(q.size()) {
    24.                   auto m = q.front();
    25.                   q.pop();
    26.                   if (m) {
    27.                       return false;
    28.                   }
    29.               }
    30.               continue;
    31.           }
    32.           q.push(n->left);
    33.           q.push(n->right);
    34.       }
    35.       return true;
    36.   }
    37. };