是否为平衡二叉树（AVL）

平衡二叉树定义：任意节点的子树的高度差都小于等于 1

判断「平衡二叉树」的 2 个条件：

1. 是「二叉排序树」
2. 任何一个节点的左子树或者右子树都是「平衡二叉树」（左右高度差小于等于 1）

二叉树递归套路 #

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

class Solution {
 private:
  struct Info {
    bool isBalanced;
    int height;
    Info(bool i, int h) : isBalanced(i), height(h){};
  };

  Info *process(Node *x) {
    if (x == nullptr) return new Info(true, 0);
    Info *lInfo = process(x->left);
    Info *rInfo = process(x->right);
    int height = max(lInfo->height, rInfo->height) + 1;
    bool isBalanced = true;
    if (!lInfo->isBalanced || !rInfo->isBalanced) isBalanced = false;

    if (abs(lInfo->height - rInfo->height) > 1) isBalanced = false;
    return new Info(isBalanced, height);
  }

 public:
  bool isBalanced(Node *head) { return process(head)->isBalanced; }
};