题目

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

分析

判断给定二叉树是否为二叉平衡树，即任一节点的左右子树高度差必须小于等于1，只需要求得左右子树的高度，比较判定即可。

AC代码

class Solution {

public:

    //判断二叉树是否平衡

    bool isBalanced(TreeNode* root) {

        if (!root)

            return true;

        int lheight = height(root->left), rheight = height(root->right);

        if (abs(lheight - rheight) <= 1)

            return isBalanced(root->left) && isBalanced(root->right);

        else

            return false;

    }

    //求树的高度

    int height(TreeNode *root)

    {

        if (!root)

            return 0;

        else

            return max(height(root->left), height(root->right)) + 1;

    }

};

GitHub测试程序源码