二叉树 – 验证二叉平衡树？

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

故我们在求根节点的左右子树的深度时即判断是否不满足平衡树的条件。

这里我们采用二叉树的后序遍历来计算高度的例子来求解

class Solution {
public:
    int getHeight(TreeNode* root){
        if (root == nullptr) return 0;
        int leftHeight = getHeight(root->left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(root->right);
        if (rightHeight == -1) return -1;
        if (abs(leftHeight - rightHeight) > 1) return -1;
        else return max(leftHeight, rightHeight) + 1;
    }
    bool isBalanced(TreeNode* root) {
        if (root==nullptr) return true;
        if (getHeight(root) == -1) return false;
        else return true;
    }
};