递归三步曲分析：
参数：当前传入节点。 返回值：以当前传入节点为根节点的树的高度。
那么如何标记左右子树是否差值大于1呢？
如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。
所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。
代码如下：
// -1 表示已经不是平衡二叉树了，否则返回值是以该节点为根节点树的高度
int getHeight(TreeNode* node)
递归的过程中遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0
代码如下：
if (node == NULL) {
return 0;
}
如何判断以当前传入节点为根节点的二叉树是否是平衡二叉树呢？当然是其左子树高度和其右子树高度的差值。
分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了。
int leftHeight = getHeight(node->left); // 左
if (leftHeight == -1) return -1;
int rightHeight = getHeight(node->right); // 右
if (rightHeight == -1) return -1;
int result;
if (abs(leftHeight – rightHeight) > 1) { // 中
result = -1;
} else {
result = 1 + max(leftHeight, rightHeight); // 以当前节点为根节点的树的最大高度
}
return result;
此时递归的函数就已经写出来了，这个递归的函数传入节点指针，返回以该节点为根节点的二叉树的高度，如果不是二叉平衡树，则返回-1。
完整代码如下：
class Solution {
public:
// 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了则返回-1
int getHeight(TreeNode* node) {
// 如果节点为空，高度为0（空树高度为0）
if (node == NULL) {
return 0;
}
// 递归获取左子树的高度
int leftHeight = getHeight(node->left);
// 如果左子树已经不平衡（返回-1），直接向上传递-1，不再继续计算
if (leftHeight == -1) return -1;
// 递归获取右子树的高度
int rightHeight = getHeight(node->right);
// 如果右子树已经不平衡（返回-1），直接向上传递-1
if (rightHeight == -1) return -1;
// 判断当前节点是否平衡：
// 1. 如果左右子树高度差大于1，说明当前节点不平衡，返回-1
// 2. 否则，返回当前树的高度 = 左右子树最大高度 + 1（+1是因为要包含当前节点）
return abs(leftHeight – rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
}
bool isBalanced(TreeNode* root) {
// 调用getHeight函数：
// 1. 如果返回-1，说明树不平衡，返回false
// 2. 否则，说明树平衡，返回true
return getHeight(root) == -1 ? false : true;
}
};
举例：
3
/ \\
9 20
/ \\
15 7
/ /
4 8
/
5
isBalanced(3)
└─ getHeight(3) ← 最终返回-1
├─ getHeight(9) ← 返回1
│ ├─ getHeight(NULL) ← 返回0
│ └─ getHeight(NULL) ← 返回0
│
└─ getHeight(20) ← 返回-1
├─ getHeight(15) ← 返回2
│ ├─ getHeight(4) ← 返回1
│ │ ├─ getHeight(NULL) ← 返回0
│ │ └─ getHeight(NULL) ← 返回0
│ └─ getHeight(NULL) ← 返回0
│
└─ getHeight(7) ← 返回-1 (这里最早发现不平衡！)
├─ getHeight(8) ← 返回2
│ ├─ getHeight(5) ← 返回1
│ │ ├─ getHeight(NULL) ← 返回0
│ │ └─ getHeight(NULL) ← 返回0
│ └─ getHeight(NULL) ← 返回0
└─ getHeight(NULL) ← 返回0
