本文共 1487 字，大约阅读时间需要 4 分钟。

解法1：递归（大量重复计算，时间复杂度高）

思想：

​ 一个节点平衡 = 左子平衡 && 右子平衡 && 左子右子深度相差不超过1

所以需要定义求深度的函数

缺点：

​ 计算一个节点深度时，也计算了子节点的深度，所以计算第二层时也计算了第三层的深度，但是后面还是要计算第三层的深度，所以有很多重复计算

复杂度：

​ 时间：要遍历O(logN)层，每一层需要O(N)时间，所以O(NlogN)

代码：

class Solution {   public:    // 一个节点平衡 = 左子平衡 && 右子平衡 && 左子右子深度相差不超过1    // 所以需要求深度的函数    bool isBalanced(TreeNode* root) {           if(root == NULL)            return true;        return isBalanced(root->left) && isBalanced(root->right) && abs(maxDepth(root->left) - maxDepth(root->right)) <= 1;    }    int maxDepth(TreeNode* root){           if(root == NULL)            return 0;        return max(maxDepth(root->left), maxDepth(root->right)) + 1;    }};

解法2：后序遍历 + 剪枝

思想：

​ 对二叉树做后序遍历，从底至顶返回子树深度，若判定某子树不是平衡树则 “剪枝” (返回-1)，直接向上返回。

https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/solution/mian-shi-ti-55-ii-ping-heng-er-cha-shu-cong-di-zhi/ 看动图

复杂度：

●时间：O(N)，遍历每一个节点

●空间：O(N)，树退化为链表时需要O(N)栈空间

代码注意点：

●recur的功能？

●为什么这个代码更快？从底至顶返回子树深度，若判定某子树不是平衡树则 “剪枝” (返回-1)，直接向上返回。

代码：

class Solution {   public:    bool isBalanced(TreeNode* root) {           return recur(root) != -1;    }    //求root的深度并判断root是否平衡，不平衡直接返回-1，代表不是平衡树    int recur(TreeNode* root){           if(root == NULL)            return 0;        int left = recur(root->left);        //左子树不平衡，直接返回-1        if(left == -1)            return -1;        int right = recur(root->right);        if(right == -1)            return -1;        //如果平衡，返回深度，不平衡返回-1        return abs(left - right) <= 1 ? max(left,right) + 1 : -1;    }};