【二叉树专题】剑指 Offer 55 – II. 平衡二叉树-跟着帅地玩副业，开拓第二曲线PlayOffer

大大普通 2023年11月13日下午6:22

c++
左右节点都是平衡二叉树+本节点也是平衡二叉树=该树是平衡二叉树
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int Depth(TreeNode* root){
        if(root==NULL)return 0;
        int l=Depth(root->left);
        int r=Depth(root->right);
        return l>r?(l+1):(r+1);
    }
    bool isBalanced(TreeNode* root) {
        if(root==NULL)return true;
        if(isBalanced(root->left)&&isBalanced(root->right)){
      if(abs(Depth(root->left)-Depth(root->right))<=1)return true;
       }
      return false;
    }
};

0 赞同 0 条回复

九号球普通 2023年11月12日下午7:03

“`java
左右子树都必须是平衡二叉树，从而形成递归条件
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) >= 0;
}

 public int height(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftH = height(root.left);
    int rightH = height(root.right);
    if (leftH < 0 || rightH < 0 || Math.abs(leftH - rightH) > 1) {
        return -1;
    } else {
        return Math.max(leftH, rightH) + 1;
    }
}

}

0 赞同 0 条回复

招舟子普通 2023年8月25日下午4:17

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
if(root null){
return true;
}
int right = depth(root.right);
int left = depth(root.left);
return Math.abs(right-left)<=1 &&isBalanced(root.right) &&isBalanced(root.left);

}
public int depth(TreeNode root){
    if(root ==null){
        return 0;
    }
    int right = depth(root.right);
    int left = depth(root.left);
    return Math.max(right,left)+1;
}

}
递归

0 赞同 0 条回复

淡色花樱普通 2023年7月19日下午2:03

“`java
要判断一颗二叉树是否为平衡二叉树，我们可以通过递归的方式来解决
首先判断当前节点是否为空，如果为空，返回true
分别计算当前节点的左子树和右子树的深度，如果他们的深度差超过1，返回false
最后递归判断当前节点的左子树和右子树是否为平衡二叉树，如果都是平衡二叉树，返回true 否则返回false
Public boolean isBalanced(TreeNode root) {
return noodeHeight(root)! = -1;
}
public int nodeHeight(TreeNode root){
if(root == null) return 0;
int left = nodeHeight(root.left);
if(left == -1){
return -1;
}
int right = nodeHeight(root.right);
if(right == -1){
return -1;
}
return Math.abs(left – right )<2?Math.max(left,right)+1；-1；
}

0 赞同 0 条回复

cute. 普通 2023年7月10日下午2:22

思路：递归实现的depth函数，需要分别计算左子树、右子数的深度，并且计算左右子树的绝对值

var isBalanced = function(root) {
    if(root === null) return true;
    if(maxDepth(root) === -1) return false;
    return true;
};
var maxDepth = function(root) {
    if(root === null) return 0;
    let left = maxDepth(root.left);
    if(left === -1) return -1;
    let right = maxDepth(root.right);
    if(right === -1) return -1;
    if(Math.abs(left - right) > 1) return -1;
    return Math.max(left, right) + 1;
}

0 赞同 0 条回复

BOZ 普通 2023年7月6日下午10:27

【思路】利用了递归实现的depth函数，再利用递归思路，依次对每一个节点做左右子树高度的check
【复杂度】时间复杂度O(nlogn), 空间复杂度O(1)

class Solution {
public:
    int depth(TreeNode* root) {
        if (root == NULL) return 0;
        else return std::max(depth(root->left), depth(root->right)) + 1;
    }

    bool isBalanced(TreeNode* root) {
        if (root == NULL) return true;
        if (root->right == NULL && root->left == NULL) return true;

        if (!isBalanced(root->left) || !isBalanced(root->right)) return false;
        int left = depth(root->left);
        int right = depth(root->right);
        return ((left - right >= -1) && (left - right <= 1));
    }
};

后再次进行优化，将两个递归合并，时间复杂度降为O(n)，空间复杂度变为O(n)?


class Solution {
public:
    bool _isBalanced(TreeNode* root, int &depth) {
        if (root == NULL) {
            depth = 0;
            return true;
        }

        int left, right;
        if (!_isBalanced(root->left, left) || !_isBalanced(root->right, right)) {
            return false;
        }
        depth = std::max(left, right) + 1;
        return ((left - right >= -1) && (left - right <= 1));
    }

    bool isBalanced(TreeNode* root) {
        int depth;
        return _isBalanced(root, depth);
    }

0 赞同 0 条回复

mpweixin用户普通 2023年7月6日下午1:34

C++实现

class Solution {
public:

    int maxDepth(TreeNode* root){

        if(root == nullptr) return 0;

        return max(maxDepth(root -> left), maxDepth(root -> right)) + 1;
    }

    bool isBalanced(TreeNode* root) {
        if(root == nullptr) return true;

        int leftDepth = maxDepth(root -> left);
        int rightDepth = maxDepth(root -> right);

        return abs(leftDepth - rightDepth) <= 1 && isBalanced(root -> left) && isBalanced(root -> right);

    }
};

0 赞同 0 条回复

憨憨永久会员 2023年7月5日下午6:04

通过深度搜索，来查看左右子树的深度，然后机型比较查看差值是否大于1，然后再对左右两子树再递归查看

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null)return true;

        int l=MaxPath(root.left);
        int r=MaxPath(root.right);

        return Math.abs(l-r)<=1&&isBalanced(root.left)&&isBalanced(root.right);
    }
    public int MaxPath(TreeNode root){
        if(root==null)return 0;

        return Math.max(MaxPath(root.left),MaxPath(root.right))+1;
    }
}

0 赞同 0 条回复

CV大神普通 2023年7月4日下午9:15

public boolean isBalanced(TreeNode root) {
        return nodeHeight(root) != -1;
    }

    public int nodeHeight(TreeNode root) {
        if (root == null) return 0;
        int left = nodeHeight(root.left);
        if (left == -1) {
            return -1;
        }
        int right = nodeHeight(root.right);
        if (right == -1) {
            return -1;
        }
        //左右高度之差是否<2，是就是平衡的，返回节点高度，否则返回-1，告诉上面不是平衡的
        return Math.abs(left - right) < 2 ? Math.max(left, right)+1 : -1;
    }

时间复杂度O（n）,空间复杂度O(n)

0 赞同 0 条回复

Sexypig. 普通 2023年7月4日下午3:14

要判断一棵二叉树是否为平衡二叉树，我们可以通过递归的方式来解决。
首先，判断当前节点是否为空，如果为空，则返回True。
然后，分别计算当前节点的左子树和右子树的深度，如果它们的深度差超过1，则返回False。
最后，递归地判断当前节点的左子树和右子树是否为平衡二叉树，如果都是平衡二叉树，则返回True，否则返回False。

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if not root:
            return True
        if abs(self.getDepth(root.left) - self.getDepth(root.right)) > 1:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)

    def getDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        return max(self.getDepth(root.left), self.getDepth(root.right)) + 1

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月4日上午11:50

递归

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }
    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

0 赞同 0 条回复

小金子普通 2023年7月3日下午11:21

/**时间复杂度O(n)
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isBalanced(root *TreeNode) bool {
_,b:=Height(root)
return b
}

func Height(root *TreeNode) (int,bool) {
if rootnil{
return 0,true
}

l,t:=Height(root.Left)
if !t {
    return 0,false
}
r,b:=Height(root.Right)
if !b {
    return 0,false
}
if l-r==0||l-r==1{
    return l+1,true
}else if l-r==-1{
    return r+1,true
}else{
    return 0,false
}

}

0 赞同 0 条回复

mpweixin用户普通 2023年7月2日下午3:05

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        // int left = maxDepth(root.left);
        // int right = maxDepth(root.right);
        // return (Math.abs(left - right) <= 1) && isBalanced(root.left) && 
        //     isBalanced(root.right );
        if(judgeDepth(root) == -1) {
            return false;
        }
        return true;
    }

    public int judgeDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = judgeDepth(root.left);
        if(left == -1) {
            return -1;
        }
        int right = judgeDepth(root.right); 
        if(right == -1) {
            return -1;
        }
        if(Math.abs(left - right) > 1) {   //如果有任何一个节点不是AVL，那么整体就可以返回-1
            return -1;
        }
        return (left > right ? left : right) + 1;

    }
}

时间复杂度O(n), 空间复杂度O(n)

0 赞同 0 条回复

花老爷普通 2023年6月30日上午8:46

dfs
时间：O(n)
空间：O(n)

class Solution {
    boolean ans = true;

    public boolean isBalanced(TreeNode root) {
        dfs(root);
        return ans;
    }

    public int dfs(TreeNode root) {
        if (!ans || root == null) {
            return 0;
        }
        int left = dfs(root.left);
        int right = dfs(root.right);
        if (Math.abs(left - right) > 1) {
            ans = false;
        }
        return Math.max(left + 1, right + 1);
    }
}

0 赞同 0 条回复

拾陆. 普通 2023年6月29日下午10:36

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root == nullptr) return true;
        int left = getDepth(root->left);
        int right = getDepth(root->right);
        return abs(left - right) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
    int getDepth(TreeNode* root){
        if(root == nullptr) return 0;
        int left = getDepth(root->left);
        int right = getDepth(root->right);
        return max(left, right) + 1;
    }
};

可以

0 赞同 0 条回复

地平线真勇敢普通 2023年6月29日上午9:28

public boolean isBalanced(TreeNode root) {
if(root null) return true;
if(maxDepth(root) -1) return false;
return true;
}
public int maxDepth(TreeNode root){
if(root null) return 0;
int left = maxDepth(root.left);
if(left -1) return -1;
int right = maxDepth(root.right);
if(right -1) return -1;

    if(Math.abs(left - right)>1) return -1;
    return Math.max(left,right) + 1;
}

时间复杂度：o(n)
空间复杂度：o(n)

0 赞同 0 条回复

mpweixin用户普通 2023年6月29日上午6:12

时间复杂度: O(n)
空间复杂度: O(n)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    bool isBalance = true;
public:
    bool isBalanced(TreeNode* root) {
        checkBalance(root);
        return isBalance;
    }
    int checkBalance(TreeNode* node) {
        if (!node) {
            return 0;
        }
        int left = checkBalance(node->left);
        int right = checkBalance(node->right);
        if (abs(left - right) > 1) {
            isBalance = false;
        }
        return max(left, right) + 1;
    }
};

0 赞同 0 条回复

别恰冰水🧊 永久会员 2023年6月28日下午5:08

时间复杂度： O(n), 空间复杂度：O(n)

bool isBalanced(struct TreeNode* root) {
    if(root = NULL) return true;
    if (tree(root) == -1)   return false;
    return true;
}

int tree(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = tree(root->left);
    int rightHeight = tree(root->right);
    if (leftHeight == -1 || rightHeight == -1 || fabs(leftHeight - rightHeight) > 1) {//
        return -1;
    } else {
        return fmax(leftHeight, rightHeight) + 1;
    }
}

0 赞同 0 条回复

局外人普通 2023年6月28日上午12:18

思路：自底向上，计算左右子树高度差
时间复杂度： O(n), 空间复杂度：O(n)

class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root)==-1 ? false : true;
    }

    public int recur(TreeNode root){
        if(root==null)  return 0;

        int left = recur(root.left);
        if(left==-1)    return -1;

        int right = recur(root.right);
        if(right==-1)   return -1;

        return Math.abs(left-right)<2 ? Math.max(left, right)+1 : -1;
    }
}

0 赞同 0 条回复

张君雅小妹妹普通 2023年6月27日下午10:12

时间复杂度：O(N)
空间复杂度：O(N)

class Solution {

    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int len = depth(root);
        return len == -1 ? false : true;
    }

  // 1. 明确函数功能
    public int depth(TreeNode node){
        // 2. 寻找递归结束的条件
        if(node == null) return 0;
        // 3. 找出函数的等价关系式
        int lD = depth(node.left);
        if(lD == -1) return -1;
        int rD = depth(node.right);
        if(rD == -1) return -1;
        if(Math.abs(lD - rD) > 1) return -1;
        return Math.max(lD, rD) + 1;

    }
}

0 赞同 0 条回复

小吕普通 2023年6月27日下午4:01

c++递归：
int getmaxdep(TreeNode* temp)
{
if(tempNULL)return 0;
int leftdep = getmaxdep(temp->left);
if(leftdep-1) return -1;
int rightdep = getmaxdep(temp->right);
if(rightdep-1) return -1;
return abs(leftdep-rightdep)>1?-1:1+max(leftdep,rightdep);
}
bool isBalanced(TreeNode* root) {

    return getmaxdep(root)==-1?false:true;
}

0 赞同 0 条回复

～普通 2023年6月26日下午11:03

class Solution {
bool res = true;
public:
bool isBalanced(TreeNode* root) {
int depth = MaxDepth(root);
return res;
}
int MaxDepth(TreeNode* root){
if(rootnullptr){
return 0;
}
int leftdepth = MaxDepth(root->left);
int rightdepth = MaxDepth(root->right);
if(abs(rightdepth-leftdepth)>1){
res = false;
}
return 1+max(leftdepth,rightdepth);
}
};
时间复杂度O（N）

0 赞同 0 条回复

普通 2023年6月26日下午4:14

class Solution {
    boolean isBalanced = true;
    public boolean isBalanced(TreeNode root) {
        maxDepth(root);
        return isBalanced;
    }

    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        int len = Math.abs(left-right);
        if(len>1){
            isBalanced = false;
        }
        int maxLen = Math.max(left,right) + 1;
        return maxLen;
    }
}

后序遍历DFS,时间复杂度 O(n)
遍历过程中判断左右子树深度相差

0 赞同 0 条回复

mpweixin用户普通 2023年6月26日下午2:41

int height(struct TreeNode*root)
{
  if(root==NULL)
  {
      return 0;
  }
  else
  {
      return fmax(height(root->left),height(root->right))+1;
  }

}
bool isBalanced(struct TreeNode* root) {
    if(root==NULL)
    {
        return true;
    }
    else
    {
return fabs(height(root->left)-height(root->right))<=1&&isBalanced(root->left) && isBalanced(root->right);
    }
    }

时间复杂度为 O(n)
空间复杂度为 O(n)

0 赞同 0 条回复

Bello~ 普通 2023年6月26日下午2:35

自丁向下递归
时间复杂度O(N²)最坏
空间复杂度O(N)

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && 
        isBalanced(root.left) && isBalanced(root.right);
    }

    private int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}

0 赞同 0 条回复

残月冷骄阳普通 2023年6月26日上午11:18

复杂度

时间复杂度: $O(n)$
空间复杂度: $O(n)$

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        return maxDepth(root)==-1 ?false:true;

    }
    public int maxDepth(TreeNode root){
        if(root==null){
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        if(left==-1|| right==-1|| Math.abs(left-right)>1) return -1;
        return Math.max(left,right)+1;
    }
}

0 赞同 0 条回复

彦，，# 普通 2023年6月26日上午12:51

//递归

public:
    int getHigh(TreeNode* root){
        if(!root) return 0;
        int high_left = getHigh(root->left);
        int high_right = getHigh(root->right);
        if(high_left == -1 || high_right == -1 ||abs(high_left - high_right) >1)
        {
            return -1;
        }else{
            return max(high_left,high_right) +1;
        }
    }
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        return getHigh(root) >=0 ;

    }
};

0 赞同 0 条回复

Jerry 普通 2023年6月25日下午10:50

 //递归
class Solution {
    public boolean isBalanced(TreeNode A, TreeNode B) {
        if (root == null) return true;
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 //左右子树的高度差不超过 1
                && isBalanced(root.left)    //左右子树也都是 平衡二叉树
                && isBalanced(root.right);
    }

    boolean depth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}

时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

Tlhey 普通 2023年6月25日下午10:44

“`
class Solution {
private:
int recur(TreeNode* root){
if(root==nullptr)return 0;
int l = recur(root->left);
if(l==-1) return -1;
int r = recur(root->right);
if(r==-1) return -1;
return (l-r<=1 && l-r>=-1) ? max(l,r)+1 : -1;
}
public:
bool isBalanced(TreeNode* root) {
return recur(root)!=-1;
}//中文

};
“`

0 赞同 0 条回复

硬核洋葱普通 2023年6月25日下午9:08

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        bool ans = true;
        nodeheight(root, ans);
        return ans;
    }

    int nodeheight(TreeNode* p, bool& ans){
        if(!p)  return 0;
        if(!ans)    return -1;

        int leftheight = nodeheight(p->left, ans);
        if(!ans)
            return -1;
        int rightheight = nodeheight(p->right, ans);
        if(rightheight - leftheight > 1 || leftheight - rightheight > 1)
            ans = false;
        return max(rightheight, leftheight) + 1;
    }
};

自底向上递归算该节点的深度，且在递归的过程中判断，如果发现下面的节点不满足平衡二叉树的条件就直接返回，剪枝
更好的书写方式是如果本节点及下面的节点不满足平衡二叉树的条件，高度返回-1
时间复杂度 O(n) 空间复杂度 O(h)

0 赞同 0 条回复

屠龙手段普通 2023年6月25日下午8:30

递归
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if not root:
            return True
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        if abs(left_depth - right_depth) > 1:
            return False
        left = self.isBalanced(root.left)
        right = self.isBalanced(root.right)
        return left and right

    def maxDepth(self, root: TreeNode) -> bool:
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

0 赞同 0 条回复

伏月三十普通 2023年6月25日下午8:16

时间复杂度 O(n) 空间复杂度O(n)

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        if(shendu(root)==-1){
            return false;
        }
        return true;
    }

    private int shendu(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=shendu(root.left);
        //如果当前左节点已经不是平衡二叉树了
        if(left==-1){
            return -1;
        }
        int right=shendu(root.right);
        //如果当前右节点已经不是平衡二叉树了
        if(right==-1){
            return -1;
        }

        //当前节点左右子树的深度
        if(Math.abs(left-right)>1){
            return -1;
        }

        //否则就返回当前节点的深度
        return Math.max(left,right)+1;
    }
}

0 赞同 0 条回复

Dsjh 普通 2023年6月25日下午8:09

// c++实现
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(!root){
            return true;
        }
        if(isBalanced(root->left)&&isBalanced(root->right)){
            int l = deth(root->left);
            int r = deth(root->right);
            if(abs(l-r) <= 1)
                return true;
        }
        return false;
    }
    int deth(TreeNode* root){
        if(!root){
            return 0;
        }
        return max(1+deth(root->left),1+deth(root->right));
    }
};

0 赞同 0 条回复

张开怀普通 2023年6月25日下午3:56

class Solution(){
public:
      bool isBalanced(TreeNode* root){
            if(root == nullptr) return true;
            if(maxDepth(root) == -1) return false;
            return true;
      }

      int maxDepth(TreeNode* root){
            if (root == nullptr) return 0;
            int left = maxDepth(root->left);
            if(left == -1) return -1;
            int right = maxDepth(root->right);
            if(right == -1) return -1;

            if (abs(left - right) > 1) return -1;
            return max(left,right) + 1;
      }
}

时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

désire. 普通 2023年6月25日上午10:53

C++递归实现：
class Solution {
public:
int getDepth(TreeNode* node)
{
if(node NULL) return 0;
int leftHeight = getDepth(node->left);
if(leftHeight -1) return -1;
int rightHeight = getDepth(node->right);
if(rightHeight -1) return -1;
return abs(leftHeight – rightHeight) > 1 ? -1 : 1 + max(leftHeight,rightHeight);
}
bool isBalanced(TreeNode* root)
{
if(root NULL) return true;
return getDepth(root) -1 ? false : true;
}
};

0 赞同 0 条回复

Vow the vow。普通 2023年6月25日上午8:57

采用自底向上的方法来计算深度，时间复杂度为O(n)。如果采用自顶向下的方式，需要对每棵子树都进行相应的操作，时间复杂度为O(n^2)。

// 自底向上
    public boolean isBalanced(TreeNode root) {
        return getDepth(root) != -1;
    }

    public int getDepth(TreeNode node){
        if(node == null) return 0;
        int leftDepth = getDepth(node.left);
        if(leftDepth == -1) return -1;
        int rightDepth = getDepth(node.right);
        if(rightDepth == -1) return -1;
        if(Math.abs(leftDepth-rightDepth) > 1) return -1;
        return Math.max(leftDepth, rightDepth) + 1; 
    }

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年6月25日上午2:21

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:

        balanced = [1]

        def isBalancedHelper(root):

            if not balanced[0] or not root:
                return 0

            leftHeight = isBalancedHelper(root.left)
            rightHeight = isBalancedHelper(root.right)

            if abs(leftHeight - rightHeight) > 1:
                balanced[0] = 0

            return 1 + max(leftHeight, rightHeight)

        isBalancedHelper(root)
        return balanced[0]

balanced必须为array, 因为这样才能让nested function改变他的val. 如果使用int, nested function treats all outer scope variables as local unless explicitly use nonlocal

0 赞同 0 条回复

大鑫啊普通 2023年6月25日上午1:40

时空复杂度：O(n)
1、递归判断平衡二叉树时，可能存在很多的重复计算
2、在深度方法中可以根据深度差值直接返回-1
3、在递归判断平衡二叉树时，可根据深度方法是否返回-1来直接返回false
4、返回值不为-1，则结果是返回true

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null)return true;
        if(maxDepth(root) == -1)return false;
        return true;
    }
    public int maxDepth(TreeNode root) {
        if(root == null)return 0;
        int left = maxDepth(root.left);
        if(left == -1) return -1;
        int right = maxDepth(root.right);
        if(right == -1) return -1;
        if(Math.abs(left - right) > 1){
            return -1;//返回-1表示不满足平衡二叉树条件
        }
        return Math.max(left,right)+1;
    }
}

0 赞同 0 条回复

怀瑾永久会员 2023年6月24日下午11:06

时间复杂度：O（n）
空间复杂度：O（n）
思路：首先递归求解树的深度，一旦左右子树深度>1，就不是平衡二叉树，优化思想是：如果父节点已经判断出不是平衡节点，那么就不用对子节点继续遍历判断。

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root == NULL) return true;
        if(Depth(root) == -1) return false;
        return true;
    }
    int Depth(TreeNode* root){
        if(root == NULL) return 0;
        int left = Depth(root->left);
        if(left == -1) return -1;
        int right = Depth(root->right);
        if(right == -1) return -1;
        if(abs(left-right) > 1) return -1;
        return max(left, right)+1;
    }
};

0 赞同 0 条回复

江畅普通 2023年6月24日下午10:53

// 判断是否是平衡二叉树
// 时间复杂度 O(N)
// 空间复杂度 O(N)
class Solution {
private:
    // 计算以 root 为节点的平衡二叉树的高度
    // 若为平衡二叉树，则返回其高度
    // 不为平衡二叉树，返回 -1
    int height(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }

        // 不为平衡二叉树，返回 -1
        if (height(root->left) == -1 || height(root->right) == -1 ||
            abs(height(root->left) - height(root->right)) > 1) {
            return -1;
        }

        return max(height(root->left), height(root->right)) + 1;
    }

public:
    bool isBalanced(TreeNode* root) { return height(root) >= 0; }
};

0 赞同 0 条回复

Ming 普通 2023年6月24日下午10:30

时间复杂度O(nlogn)，空间复杂度O(n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int l = maxDepth(root.left);
        int r = maxDepth(root.right);
        return Math.abs(l-r) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        return Math.max(left, right) + 1;
    }
}

时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        if(maxDepth(root) == -1) return false;
        return true;
    }
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int left = maxDepth(root.left);
        if(left == -1) return -1;
        int right = maxDepth(root.right);
        if(right == -1) return -1;
        if(Math.abs(left - right) > 1) return -1;
        return Math.max(left, right) + 1;
    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年6月24日下午10:28

 // 时间O(n),空间O(n)，最坏情况，遍历所有节点，递归深度是节点数
class Solution {
public:
    int MaxDepth(TreeNode* root)
    {   
        if(!root) return 0;
        int left = MaxDepth(root->left);
        if(left==-1) return -1;
        int right = MaxDepth(root->right);
        if(right==-1) return -1;
        if(abs(left-right)>1) return -1;
        return max(left,right)+1;
    }
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        if(MaxDepth(root)==-1) return false;
        return true;
    }
};

0 赞同 0 条回复

yxy 普通 2023年6月24日下午7:42

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int dfs(TreeNode* root)
    {
        if(!root) return 0;
        int l=dfs(root->left);
        int r=dfs(root->right);
        if(l==-1||r==-1)
            return -1;
        if(abs(l-r)>1)
            return -1;
        return max(l,r)+1;
    }
    bool isBalanced(TreeNode* root) {
        if(dfs(root)!=-1)
            return true;
        return false;
    }
};

时间复杂度O(n),空间复杂度O(n)

0 赞同 0 条回复

Yodl. 普通 2023年6月24日下午6:48

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int dep(TreeNode* root)
    {
        int l_dep,r_dep;
        if(root==NULL)
        {
            return 0;
        }
        l_dep=dep(root->left);
        r_dep=dep(root->right);
        return (l_dep>r_dep)?(l_dep+1):(r_dep+1);
    }

    bool isBalanced(TreeNode* root) {
        if(root==NULL)
        {
            return true;
        }
        int l_dep,r_dep,l,r;
        l=isBalanced(root->left);
        if(l==false)
        {
            return false;
        }
        r=isBalanced(root->right);
        if(r==false)
        {
            return false;
        }
        l_dep=dep(root->left);
        r_dep=dep(root->right);
        if(fabs(l_dep-r_dep)>1)
        {
            return false;
        }
        return true;
    }
};

时间复杂度O(nlogn),空间复杂度O(n)

0 赞同 0 条回复

jhfuture 普通 2023年6月24日下午4:58

public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
          if(Depth(root)==-1) return false;
          return true;
            // return Math.abs(left-right)<=1 && isBalanced(root.left)&& isBalanced(root.right);
    }


    // 
    public int Depth(TreeNode root){
        if(root==null) return 0;
        int left=Depth(root.left);
        if(left==-1) return -1;
        int right=Depth(root.right);
        if(right==-1) return -1;
        return Math.abs(left-right)>1?-1:Math.max(left,right)+1;
    }

跟着帅地的思路，二叉树是小白。
时间复杂度n，空间复杂度为n

0 赞同 0 条回复

mpweixin用户永久会员 2023年6月24日下午4:46

//时间O(n) 空间O(n)
public boolean isBalanced(TreeNode root) {
        return maxDepthWithIsBalanced(root) != -1;
    }

    public int maxDepthWithIsBalanced(TreeNode root){
        if(root == null){
            return 0;
        }

        int left = maxDepthWithIsBalanced(root.left);
        if(left == -1){
            return -1;
        }
        int right = maxDepthWithIsBalanced(root.right);
        if(right == -1){
            return -1;
        }

        return Math.abs(left - right) > 1 ? -1 : Math.max(left,right) + 1;
    }

0 赞同 0 条回复

peach 普通 2023年6月24日下午4:07

思路

使用递归逻辑
先处理终止条件。走到叶子节点返回true，如果这层的左右子树深度不满足绝对值差小于等于1，返回false
然后还要看左右子树分别是不是平衡二叉树，都是才返回true

代码

 //递归解法
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true; //终止条件，如果走到叶子节点，直接返回true
        int left = getDepth(root.left);
        int right = getDepth(root.right);//计算左子树和右子树的深度
        if(Math.abs(left - right) > 1) return false; //不符合这一层的要求，直接返回false
        return isBalanced(root.left) && isBalanced(root.right); //再看左右子树是否满足要求
    }
    private int getDepth(TreeNode root){ //计算树的深度
        if(root == null) return 0;
        return Math.max(getDepth(root.left), getDepth(root.right)) + 1;
    }
}

0 赞同 0 条回复

雨落圆荷普通 2023年6月24日下午3:41

class Solution {
// nlogn 空间 On
public boolean isBalanced(TreeNode root) {
if(root null) return true;
if(maxDepth(root) -1) return false;
return true;

}

public int maxDepth(TreeNode root) {
    if(root == null) return 0;
    int left = maxDepth(root.left);
    if(left == -1) return -1;
    int right = maxDepth(root.right);
    if(right == -1) return -1;
    // 返回-1表示不符合条件了
    if(Math.abs(left - right) > 1) return -1;

    return Math.max(left, right) + 1;
}

}

0 赞同 0 条回复

　　　　　　　　普通 2023年6月24日下午3:39

class Solution {
public:
    int dep(TreeNode* root){
        if(!root)return 0;
        return max(dep(root->right),dep(root->left))+1;
    }
    bool is(TreeNode* root){
        if(!root)return true;
        if(abs(dep(root->left)-dep(root->right))>1)return false;
        return is(root->left)&&is(root->right);
    }
    bool isBalanced(TreeNode* root) {
        return is(root);
    }
};

【时间O(nlogn),空间O(n)】
递归判断每个节点

0 赞同 0 条回复

【二叉树专题】剑指 Offer 55 – II. 平衡二叉树

共以下 49 个回答

复杂度

Code

思路

代码

# 回答此问题取消回复

【二叉树专题】剑指 Offer 55 – II. 平衡二叉树

共以下 49 个回答

复杂度

Code

思路

代码

# 回答此问题 取消回复

# 回答此问题取消回复