二叉树的完全性检验

思路：非递归，使用队列实现（队列空代表 是完全二叉树） #

bool isCompleteTree1(TreeNode *head) {
  if (head == nullptr) return true;

  queue<TreeNode *> q;
  bool leaf = false;
  TreeNode *l = nullptr, *r = nullptr;
  q.push(head);

  while (!q.empty()) {
    head = q.front();
    q.pop();
    l = head->left, r = head->right;
    if ((leaf && (l != nullptr || r != nullptr)) ||
        (l == nullptr && r != nullptr))
      return false;

    if (l != nullptr) q.push(l);
    if (r != nullptr) q.push(r);

    if (l == nullptr || r == nullptr) leaf = true;
  }
  return true;
}

二叉树的递归套路 #

完全二叉树的四种可能性

1. 左满二叉树，右满二叉树，左树高 == 右树高
2. 左完全二叉树，右满二叉树，左树高 == 右树高 + 1
3. 左满二叉树，右满二叉树，左树高 == 右树高 + 1
4. 左满二叉树，右完全二叉树，左树高 == 右树高

class Solution {
 private:
  // 二叉树递归套路实现;
  struct Info {
    bool isFull, isCBT;
    int height;
    Info(bool full, bool cbt, int h) : isFull(full), isCBT(cbt), height(h){};
  };

  Info *process(TreeNode *x) {
    if (x == nullptr) return new Info(true, true, 0);

    Info *lInfo = process(x->left);
    Info *rInfo = process(x->right);
    int height = max(lInfo->height, rInfo->height) + 1;

    bool isFull =
        lInfo->isFull && rInfo->isFull && lInfo->height == rInfo->height;
    bool isCBT = false;

    if (lInfo->isFull && rInfo->isFull && lInfo->height == rInfo->height)
      isCBT = true;
    else if (lInfo->isCBT && rInfo->isFull &&
             lInfo->height == rInfo->height + 1)
      isCBT = true;
    else if (lInfo->isFull && rInfo->isFull &&
             lInfo->height == rInfo->height + 1)
      isCBT = true;
    else if (lInfo->isFull && rInfo->isCBT && lInfo->height == rInfo->height)
      isCBT = true;

    return new Info(isFull, isCBT, height);
  };

 public:
  bool isCompleteTree2(TreeNode *head) { return process(head)->isCBT; }
};