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

class Solution {
public:
    int isIsBalancedAndHeight(TreeNode* pRoot)
    {
	  //空树返回高度0
        if(pRoot==nullptr)
            return 0;
        //获取子树高度（包含子树是否为平衡树的信息）
        int l=isIsBalancedAndHeight(pRoot->left);
        int r=isIsBalancedAndHeight(pRoot->right);
        if(l==-1||r==-1)
        {
            return -1;
        }
        else if(abs(l-r)>1)
        {
            return -1;
        }//以上两种情况可以判断该树不为平衡树
        else 
        {
            return max(l,r)+1;
        }
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        int res=isIsBalancedAndHeight(pRoot);
        if(res==-1)//按照函数定义，-1代表不为平衡树
        {
            return false;
        }
        else 
        {
            return true;
        }
    
    }
};

使用递归的方法解决此问题

1.空树为平衡树返回0

2.如果左右子树不都是平衡树，那么返回-1；

否则，判断1.根结点的左右子树高度差是否小于一，小于1返回-1，

2.否则返回当前树的高度给上一级，当前树的高度是容易得到的，因为其就等于左右子树的最高高度加1；

总结：

由于先假定能判断左右子树是否是平衡树倒推，这是后序遍历的思想