剑指offer——判断平衡二叉树

题目描述：

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

思路：

递归解法。计算左右子树的深度，若深度差大于1，return false。

代码：

语言C++，已通过牛课网在线测试。

class Solution {
public:
    //递归方法，分别计算左右子树深度，若深度差大于1，return false
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(pRoot == NULL) return true;
        int left = getDepth(pRoot->left);
        int right = getDepth(pRoot->right);
        int diff = left - right;
        if(diff > 1 || diff < -1) return false;
        return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);

    }
    int getDepth(TreeNode* pRoot){
        if(pRoot == NULL) return 0;
        int left = getDepth(pRoot->left);
        int right = getDepth(pRoot->right);
        return (left > right) ? (left + 1) : (right + 1);
    }
};