输入一棵二叉树的根结点，判断该树是不是平衡二叉树。

如果某二叉树中任意结点的左右子树的深度相差不超过 1，那么它就是一棵平衡二叉树。

注意：

规定空树也是一棵平衡二叉树。

样例

输入：二叉树[5,7,11,null,null,12,9,null,null,null,null]如下所示，
    5
   / \
  7  11
    /  \
   12   9

输出：true

参考答案

``c++ class Solution { public: bool isBalanced(TreeNode* root) { /* unit test root is nil root not nil, left is nil, right is nil root not nil, left not nil, right nil. */ int height=dfs(root); if(height>=0) return true; else return false; }

// 当非平衡时，return -1; 平衡时，return high;
// 首先判断左子树平衡与否，再判断右子树平衡与否，在判断整棵树平衡与否；
int dfs(TreeNode *root){
    if(!root) return 0;
    int left=dfs(root->left); 
    if(left<0) return -1;
    int right=dfs(root->right);
    if(right<0) return -1;
    if(abs(left-right)>1) return -1;
    return max(left,right)+1;
}

};