https://leetcode.cn/problems/balanced-binary-tree/

题面

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

110.平衡二叉树

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

110.平衡二叉树1

返回 false 。

代码（递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
// 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了就返回-1
int getHeight(TreeNode* node) {
    if (node == NULL) return 0;
    
    int leftHeight = getHeight(node->left);
    if (leftHeight == -1) return -1;
    int rightHeight = getHeight(node->right);
    if (rightHeight == -1) return -1;
    return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
}
bool isBalanced(TreeNode* root) {
    return getHeight(root) == -1 ? false : true;
}