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

题目的主要信息：

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。 平衡二叉树是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

方法一：

采用递归。用dfs递归计算每个结点的高度，如果当前遍历的结点为NULL返回0；否则，递归计算左右子树高度，当前结点的最大高度为左右子树最大高度加1。用IsBalanced_Solution递归判断是否为平衡二叉树，首先用dfs计算左右子树的高度，如果高度差大于1，返回false；否则，继续递归判断左右子树是否为平衡二叉树。 具体做法：

class Solution {
public:
    int dfs(TreeNode* root) {
        if (!root) {
            return 0;
        }
        int left = dfs(root->left);//左子树高度
        int right = dfs(root->right);//右子树高度
        return 1 + max(left, right);
    }
    bool IsBalanced_Solution(TreeNode* root) {
        if (!root){
            return true;
        }
        int left = dfs(root->left);//左子树高度
        int right = dfs(root->right);//右子树高度
        if (abs(left - right) > 1) //左右子树高度差大于1返回false
            return false;
        return IsBalanced_Solution(root->left) && IsBalanced_Solution(root->right);//递归判断
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，遍历n个结点，每个结点花$O(n)O(n)$时间遍历。
• 空间复杂度：$O(n)O(n)$，递归栈大小为n。

方法二：

采用递归，计算高度的时候同时判断。用dfs函数计算树的最大高度，flag记录整个过程中是否出现不平衡的情况。从根节点开始，如果当前结点为NULL结束递归，否则递归计算左右子树的高度，得到左右子树高度差，若高度差大于一表示当前根结点下不是平衡二叉树，flag置为0，最后返回左右子树的最大值最为该子树的高度。递归结束后，若flag为true，表示这棵树是平衡二叉树。

具体做法：

class Solution {
public:
    bool flag = 1;
    int dfs(TreeNode* root) {
        if (!root){//如果根结点为NULL,结束递归
            return 0;
        }
        int left = dfs(root->left);//左子树高度
        int right = dfs(root->right);//右子树高度
        int diff = abs(left - right);//左右子树高度差
        if (diff > 1){//高度差大于1，不是平衡二叉树
            flag = 0;
        }
        return max(left, right) + 1;//返回最大高度
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        dfs(pRoot);//递归判断
        return flag;
    }
    
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，需要遍历所有结点。
• 空间复杂度：$O(n)O(n)$，递归栈大小为n。