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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return bool布尔型
     */
   // int count;
    int height(TreeNode * pRoot) // level 表示当前的层数
    {
       // int count = 0;
        if(pRoot == nullptr)
            return 0;
    
        int left =  height(pRoot->left);
        int right =  height(pRoot-> right);
        return max(left,right) + 1;
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        // write code here
        if(pRoot == nullptr)
            return true;
       
       //printf("left:%d,right:%d\n",left,right);
        bool l = IsBalanced_Solution(pRoot ->left);
        if(!l) return false;
        bool r = IsBalanced_Solution(pRoot ->right);
        if(!r) return false;
        // 后序遍历的好处 1。可以降低时间复杂度，比如1这个节点先序把2判断了一次 然后走到2 又判断2 产生了重复计算 
        int left = height(pRoot ->left);
        int right = height(pRoot ->right);
        // 分开算高度也会产生重复计算吗，因为算1的高度的时候，已经顺带把2的高度也算出来，但是走到2的时候又会算一遍 
        // 我们把两个函数都改成后续是为了和2为1
        if(abs(left - right)> 1) return false;
        return true;
       
       
       // printf("l:%d,r:%d\n",l,r);
       //return false;
        return l && r;
    }
  // 方法2
   int dfs(TreeNode* root)  // 因为既要返回 是否是平衡二叉树的bool值 又要返回高度 
	 // 所以我们规定返回 -1 为不是平衡二叉树 其他就是高度
    {
        if(root == nullptr) return 0;
        int left = dfs(root->left);
        if(left == -1) return -1;
        int right = dfs(root->right);
        if(right== -1) return -1;
        return abs(left -right ) <= 1 ? max(left,right) +1 : -1;

    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
       return dfs(pRoot) != -1;
    }
};