题解 | #判断是不是平衡二叉树#

思路：

平衡二叉树任意节点两边的子树深度相差绝对值不会超过1，且每个子树都满足这个条件，那我们可以对每个节点找到两边的深度以后：

int deep(TreeNode root){
    if(root == null) 
        return 0;
    int left = deep(root.left); 
    int right = deep(root.right);
    //子树最大深度加上自己
    return (left > right) ? left + 1 : right + 1; 
}

判断是否两边相差绝对值超过1：

//左子树深度减去右子树相差绝对值大于1
if(left - right > 1 || left - right < -1) 
    return false;

然后因为每个子树都满足这个条件，我们还需要遍历二叉树每个节点当成一棵子树进行判断，而对于每个每个节点判断后，其子节点就是子问题，因此可以用递归。

IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);

具体做法：

step 1：第一个函数递归遍历二叉树所有节点。

step 2：对于每个节点判断，调用第二个函数获取子树深度。

step 3：第二个函数递归获取子树深度，只需要不断往子节点深度遍历，累加左右深度的较大值。

step 4：根据深度判断该节点下的子树是否为平衡二叉树。

class Solution {
public:
    int depth(TreeNode* pRoot)
    {
        if(!pRoot)
            return 0;
        return max(depth(pRoot->left),depth(pRoot->right))+1;
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(!pRoot)
            return true;
        if(abs(depth(pRoot->left)-depth(pRoot->right)) > 1)
            return false;
        return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
    }
};