题目
输入一棵二叉树的根结点，判断该树是不是平衡二叉树。
如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
注意：
规定空树也是一棵平衡二叉树。
样例
输入：二叉树[5,7,11,null,null,12,9,null,null,null,null]如下所示，
5
/ \
7 11
/ \
12 9
输出：true

解法：后序遍历

在二叉树的深度基础上判断一下左右子树的深度之间的关系即可
时间复杂度O(n)，空间复杂度O(1)

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     bool ans = true;
  14.     bool isBalanced(TreeNode* root) {
  15.         dfs(root);
  16.         return ans;
  17.     }
  19.     int dfs(TreeNode *u) {
  20.         if (!u) return 0;
  22.         int dl = dfs(u->left);
  23.         int dr = dfs(u->right);
  25.         if (abs(dl - dr) > 1) ans = false;
  26.         return max(dl, dr) + 1;
  27.     }
  28. };