是否为完全二叉树

若设二叉树的深度为 h，除第 h 层外，其它各层 (1 ～ h-1) 的结点数都达到最大个数(即 1~h-1 层为一个满二叉树);叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。

二叉树递归套路 #

1. 假设以 X 节点为头，假设可以向 X 左树和 X 右树要任何信息
2. 在上一步的假设下，讨论以 X 为头节点的树，得到答案的可能性（最重要）
3. 列出所有可能性后，确定到底需要向左树和右树要什么样的信息
4. 把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息 S
5. 递归函数都返回 S，每一棵子树都这么要求
6. 在代码中考虑如何把左树的信息和右树信息整合出整棵树的信息

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(Node *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 (isFull)
      isCBT = true;
    else {
      if (lInfo->isCBT && rInfo->isCBT) {
        if (lInfo->isCBT && rInfo->isFull && lInfo->height == rInfo->height + 1)
          isCBT = true;
        if (lInfo->isFull && rInfo->isFull &&
            lInfo->height == rInfo->height + 1)
          isCBT = true;
        if (lInfo->isFull && rInfo->isCBT && lInfo->height == rInfo->height)
          isCBT = true;
      }
    }
    return new Info(isFull, isCBT, height);
  }

 public:
  bool isCBT(Node *head) {
    if (head == nullptr) return true;
    return process(head)->isCBT;
  };
};