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

//首先说一下，二叉树的树形dp套路简直不要太好用，不会的小伙伴可以去b站上搜左程云看他的算法视频，讲的超级好

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        //这题利用二叉树的树形dp套路无脑解就行了
        //首先分析一下可能性：我需要左右子树是否是平衡二叉树的信息，还需要左右子树各自的高度就行了
        //ok，分析完毕
        return process(pRoot).isBst;
        
    }
    struct Info{
        bool isBst;
        int high;
    };
    Info process(TreeNode* pRoot)
    {
        if(pRoot==NULL)//base case空树的高度是0而且空树也认为是平衡二叉树
        {
            Info data;
            data.high=0;
            data.isBst=true;
            return data;
        }
        Info leftDta=process(pRoot->left);//问左子树要信息
        Info rightData=process(pRoot->right);//问右子树要信息
        //现在头结点要综合信息并向上返回
        Info nowData;
        if(leftDta.isBst==true&&rightData.isBst==true&&abs(leftDta.high-rightData.high)<=1)
            nowData.isBst=true;
        else nowData.isBst=false;
        nowData.high=max(leftDta.high,rightData.high)+1;
        return nowData;
    }
};