打印二叉树

高度为 h，并且由 –1 个结点的二叉树，被称为满二叉树，其实不难看出，满二叉树的结点的度要么为 0（叶子结点），要么为 2（非叶子结点）

二叉树递归套路 #

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

class Solution {
 private:
  struct Info1 {
    int height, nodes;
    Info1(int h, int n) : height(h), nodes(n){};
  };

  Info1* process1(Node* head) {
    if (head == nullptr) return new Info1(0, 0);
    Info1* lInfo = process1(head->left);
    Info1* rInfo = process1(head->right);

    int height = max(lInfo->height, rInfo->height) + 1;
    int nodes = lInfo->nodes + rInfo->nodes + 1;
    return new Info1(height, nodes);
  }

  struct Info2 {
    bool isFull;
    int height;
    Info2(bool f, int h) : isFull(f), height(h){};
  };

  Info2* process2(Node* head) {
    if (head == nullptr) return new Info2(true, 0);

    Info2* lInfo = process2(head->left);
    Info2* rInfo = process2(head->right);
    bool isFull =
        lInfo->isFull && rInfo->isFull && lInfo->height == rInfo->height;
    int height = max(lInfo->height, rInfo->height) + 1;
    return new Info2(isFull, height);
  }

 public:
 // 只有满二叉树满足 : 2 ^ h - 1 == n
  bool isFull1(Node* head) {
    if (head == nullptr) return true;
    Info1* all = process1(head);
    return (1 << all->height) - 1 == all->nodes;
  }

  // 左树满 && 右树满 && 左右树高度一样 -> 整棵树是满的
  bool isFull2(Node* head) {
    if (head == nullptr) return true;
    return process2(head)->isFull;
  }
};