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

sasuke 普通 2023年4月3日下午2:56

class Solution {
    public boolean isBalanced(TreeNode root) {
        //计算左子树高度，计算右子树高度，判断是否绝对值相差大于一
        //绝对值 Math.abs()
        int res = getHeight(root);
        if(res == -1){
            return false;
        }
        return true;

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

0 赞同 0 条回复

宁永久会员 2023年3月10日上午10:09

class Solution {
    public boolean isBalanced(TreeNode root) {
        //计算左子树高度，计算右子树高度，判断是否绝对值相差大于一
        //绝对值 Math.abs()
        int res = getHeight(root);
        if(res == -1){
            return false;
        }
        return true;

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

0 赞同 0 条回复

lucca 普通 2023年1月3日下午2:57

O(N^2) 递归

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

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

O(N) 记忆化搜索，不过优化表现并不好

class Solution {
    Map<TreeNode, Integer> map = new HashMap<>();

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

    private int height(TreeNode root) {
        Integer res = map.get(root);
        if (res != null) return res;

        if (root == null) res = 0;
        else res = Math.max(height(root.left), height(root.right)) + 1;

        map.put(root, res);
        return res;
    }
}

O(N) 递归求高度的同时判断是否平衡，不平衡就使用特殊量返回（-1）

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    private int height(TreeNode root) {
        if (root == null) return 0;
        int l = height(root.left);
        int r = height(root.right);
        if (l == -1 || r == -1 || Math.abs(l-r) > 1) return -1;
        else return Math.max(l, r) + 1;
    }
}

0 赞同 0 条回复

PatNick 普通 2022年12月20日下午4:59

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if root == None:
            return True

        if self.maxDepth(root) == -1:
            return False
        return True


    def maxDepth(self,root: TreeNode):
        if root == None:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        if left == -1:
            return -1
        if right == -1:
            return -1
        # 左右字数高度相差大于1
        if abs(left-right)>1:
            return -1
        return max(left,rig

0 赞同 0 条回复

如梦似歌普通 2022年12月14日下午7:40

/**
 * 思路: 仍然是递归计算根结点的左右子树的深度，然后比较左右子树之差是否小于等于1即可
 * 时间复杂: T(n) = O(nlogn) 
 * 空间复杂度: S(n) = O(n) 空间复杂度主要取决于递归调用的层数，最差情况下（树退化为链表时），系统递归需要使用 O(N)的栈空间
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        //空二叉树是一个平衡二叉树
        if(root == null){
            return true;
        }
        //如果以root为结点的左右子树的深度相差不超过1，并且任意一个结点的左右子树均是平衡二叉树，那么属于平衡二叉树，否则就不是
        if(Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right))
            return true;
        else
            return false;
    }

    //计算二叉树的深度
    public int maxDepth(TreeNode root){
        if(root == null){
            return 0;  //如果树为空，则返回0
        }
        //否则递归计算左子树深度m，递归计算右子树深度n，最后树的深度为m和n中较大者加1
        return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
    }
}

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:07

class Solution {
public:
    int height(TreeNode* root){
        if(root==nullptr) return 0;
        int leftheight = height(root->left);
        int rightheight = height(root->right);//后续遍历，返回子节点的深度
        if(leftheight==-1||rightheight==-1||abs(leftheight-rightheight)>1) return -1;
        int result = 1+max(leftheight,rightheight);
        return result;
    } 
    bool isBalanced(TreeNode* root) { //
        int flag = height(root);
        return flag==-1?false:true;

    }
};

0 赞同 0 条回复

mpweixin用户普通 2022年11月18日下午1:54

C++
1. 先考虑平衡二叉树的判断：深度不能相差1
2. 递归遍历整个数
3. 递归退出条件就是递归到叶子节点

/**
* 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) {
if(root NULL) return true;
else if(root != NULL && root->left NULL && root->right NULL) return true;
if(abs(Depth(root->right)-Depth(root->left)) > 1) return false;
return isBalanced(root->right) && isBalanced(root->left);
}
int Depth(TreeNode* root) {
if(root NULL) return 0;
if(root != NULL && root->left NULL && root->right NULL) return 1;
return max(Depth(root->right)+1, Depth(root->left)+1);
}
};

0 赞同 0 条回复

cute. 普通 2022年11月12日下午7:47

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;
    var left = maxDepth(root.left);
    if(left == -1) return -1;
    var right = maxDepth(root.right);
    if(right == -1) return -1;
    // 返回-1表示不符合条件
    if(Math.abs(left - right) > 1) return -1;
    return Math.max(left, right) + 1;
}

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

0 赞同 0 条回复

xye 普通 2022年11月11日下午9:18

时间O(N),空间O(N)

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return height(root) >= 0

}

func height(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := height(root.Left)
    right := height(root.Right)
    if left == -1 || right == -1 || abs(left - right) > 1 {
        return -1
    }
    return max(left, right) + 1
}

func max(x, y int) int {
    if x < y {
        return y
    }
    return x
}

func abs(x int) int {
    if x < 0 {
        return -1 * x
    }
    return x
}

0 赞同 0 条回复

symbol 普通 2022年11月7日上午10:00

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    //判断左右子树是否为平衡二叉树
    isLeft := isBalanced(root.Left)
    isRigth := isBalanced(root.Right)

    //求左右子树的高度
    l_h := Hight(root.Left)
    r_h := Hight(root.Right)

    return abs(l_h - r_h) <=1 && isLeft && isRigth
}
func Hight(root *TreeNode) int {
    if root == nil{
        return 0
    }
    return max(Hight(root.Left), Hight(root.Right)) + 1
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
//求绝对值函数
func abs(x int) int {
    if x < 0{
        return -1 * x
    }
    return x
}
时间复杂度：O(n^2)，其中 n 是二叉树中的节点个数。
最坏情况下，二叉树是满二叉树，需要遍历二叉树中的所有节点，时间复杂度是 O(n)。
对于节点 p，如果它的高度是 d，则 height(p) 最多会被调用 d 次（即遍历到它的每一个祖先节点时）。对于平均的情况，一棵树的高度 h 满足 O(h)=O(logn)，因为 d ≤h，所以总时间复杂度为 O(nlogn)。对于最坏的情况，二叉树形成链式结构，高度为 O(n)，此时总时间复杂度为 O(n^2)。

空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n。

0 赞同 0 条回复

星河普通 2022年11月3日下午9:09

后序
class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }
    private 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;
    }
}
时间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;
    }
}
时间O(N)空间O(N)

0 赞同 0 条回复

Asphyxia 普通 2022年11月2日下午11:01

可以剪枝，自底而上，下面不平衡了后面也不要判定了

“`cpp
“`

0 赞同 0 条回复

感到自己好渺小普通 2022年11月2日下午10:11

class Solution {
    int MaxDepth(TreeNode root){  //计算结点为root的二叉树的深度
        if(root == null){
            return 0;
        }
        return Math.max(MaxDepth(root.left),MaxDepth(root.right))+1;
    }
    public boolean isBalanced(TreeNode root) {

        //如果root为空，说明是一个空二叉树，空二叉树是平衡二叉树，返回true
            if(root == null){
                return true;
            }

        //分别求以 root 为结点左右子树的深度
            int l = MaxDepth(root.left);
            int r = MaxDepth(root.right);

        //如果以 root 为结点的左右子树深度相差超过1，那么不属于平衡二叉树
            boolean ans = true;
            if(Math.abs(l-r)>1) return false;

        //利用递归分别每个节点的左右子树是否属于平衡二叉树
            boolean left = isBalanced(root.left);
            boolean right = isBalanced(root.right);
            return ans && left && right;
    }
}

0 赞同 0 条回复

一只骆驼普通 2022年11月2日上午10:26

可以在计算树的深度的时候加一个剪枝

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

0 赞同 0 条回复

cxxz 普通 2022年11月1日下午5:03

自己的思路笨重。学习帅老师的剪枝思路，在计算深度的时候就顺便算了，这也给自己一个启示就是当能在一次操作完成的事情，尽量不重复两次。但是要多思考(:

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

    // 在计算深度的时候就可以判断左右子树深度之差了
    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 (abs(left - right) > 1) return -1;

        return max(left, right) + 1;
    }

时间复杂度 O(N)： N 为树的节点数；最差情况下，需要递归遍历树的所有节点。
空间复杂度 O(N)：最差情况下（树退化为链表时），系统递归需要使用 O(N)的栈空间。

0 赞同 0 条回复

Y7n05h 普通 2022年10月31日下午9:48

class Solution {
    int depth(TreeNode *root) {
        if (!root) return 0;
        auto left = depth(root->left);
        if (left == -1) return -1;

        auto right = depth(root->right);
        if (right == -1) return -1;

        return abs(left - right) <= 1 ? std::max(left, right) + 1 : -1;
    }

public:
    bool isBalanced(TreeNode *root) {
        return depth(root) != -1;
    }
};

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

0 赞同 0 条回复

马啸天永久会员 2022年10月31日下午2:47

    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 条回复

云雾里普通 2022年10月31日上午7:27

class Solution {
    //bfs后序排序，剪枝
    public boolean isBalanced(TreeNode root) {
        return digui(root)!=-1;
    }
    private int digui(TreeNode root){
        if (root==null){
            return 0;
        }
        int left = digui(root.left);
        if(left==-1)return -1;
        int right = digui(root.right);
        if(right==-1)return -1;
        return Math.abs(left-right)<2?Math.max(left,right)+1:-1;
    }
    /*public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }*/
}

0 赞同 0 条回复

刺猬普通 2022年10月30日下午8:39

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root == nullptr)
            return true;
        if((abs(height(root->left) - height(root->right)) <= 1) && isBalanced(root->left) && isBalanced(root->right))
            return true;
        else
            return false;

    }
    int height(TreeNode* root) {
        if(root == nullptr)
            return 0;
        return max(height(root->left) , height(root->right)) + 1;
    }
};

时间复杂度：O(n^2)
空间复杂度：O(N)

0 赞同 0 条回复

小肸永久会员 2022年10月30日下午3:02

思路一：前序遍历的方式判断以每一个节点为根节点的树是否是平衡二叉树，需要写个getHeight()函数取得每一个节点的深度。前序遍历需要遍历每一个节点一次，对于每一个节点p，getHeight(p)最多被调用d次(getHeight(p)在遍历到p的祖先节点都会被调用)，d为p的高度，对于一个树来说，树的高度一般为logN，d为p节点的高度，所以d<=logN，所以一般的时间复杂度为O(NlogN)，对于链式结构的树，时间复杂度为(N^2)。

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
        }
    }
}

思路二：前序遍历对于同一个节点会重复调用它的getDepth(TreeNode)函数，可以采用后序遍历的方式，自低而上的递归，先递归的判断其左右子树是否平衡，当判断以该节点为根节点的树是否是平衡二叉树，如果是返回它的深度，否则返回-1。

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

0 赞同 0 条回复

Chin 普通 2022年10月30日下午3:00

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        //  左右高度的差值小于等于1， 注意同时满足后两个条件
        return Math.abs(height(root.left) - height(root.right)) <= 1 
        && isBalanced(root.left) 
        && isBalanced(root.right);
    }

    //  求高度
    public int height(TreeNode root){
        if(root==null) return 0;
        return Math.max(height(root.left),height(root.right))+1;
    }
}

时间复杂度On
空间复杂度On

0 赞同 0 条回复

cxc 普通 2022年10月30日下午2:42

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
//判断左子树和右子树的高度是否相差1以内，并且左子树和右子树都需要是平衡的
        return Math.abs(height(root.left) - height(root.right))<=1 && isBalanced(root.left) && isBalanced(root.right);
    }

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

0 赞同 0 条回复

天然普通 2022年10月29日下午10:40

递归还是经验不足，写的太少了

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

    def find(self,root):
        if not root: return 0
        return max(self.find(root.left),self.find(root.right))+1

0 赞同 0 条回复

lobort 普通 2022年10月29日下午10:08

class Solution {
    public boolean isBalanced(TreeNode root) {
//判断特殊情况
        if(root == null){
            return true;
        }
//调用递归函数
        if(maxDepath(root)==-1){
            return false;
        }
        return true;

    }
    public int maxDepath(TreeNode root){
        if(root == null){
            return 0;
        }
//设置递归函数  判断退出的条件
        int left = maxDepath(root.left);
        if (left == -1){
            return -1;
        }
        int right = maxDepath(root.right);
        if (right == -1){
            return -1;
        }
        if(Math.abs((left - right))>1){
            return -1;
        }
        return Math.max(left,right)+1;
    }
}

时间空间O(n)

0 赞同 0 条回复

酥合普通 2022年10月29日下午9:21

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;
        }
    }
}

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

0 赞同 0 条回复

猫猫真可爱普通 2022年10月29日下午7:15

迭代，参考上一题思路，判断左右子树高度差

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null)
            return true;
        int BL = maxDepth(root.left);
        int BR = maxDepth(root.right);
        return isBalanced(root.left)&&isBalanced(root.right)&&Math.abs(BL-BR)<2;
    }
    public int maxDepth(TreeNode root) {
        if(root == null)
            return 0;
        int L = maxDepth(root.left);
        int R = maxDepth(root.right);
        return  L>R  ?L+1 : R+1;
    }
}

0 赞同 0 条回复

阿白普通 2022年10月29日下午5:41

后序遍历递归算深度(whatever)，对于不平衡的子树返回-1，如果有任意一个子树返回-1，则递归返回-1。
时间O（n），空间O（n）

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

    int treeLevel(TreeNode *root)
    {
        if (root == nullptr)
        {
            return 0;
        }
        int l = treeLevel(root->left);
        if (l == -1)
            return -1;
        int r = treeLevel(root->right);
        if (r == -1)
            return -1;
        if (std::abs(l - r) > 1)
            return -1;
        else
            return std::max(l, r) + 1;
    }
};

0 赞同 0 条回复

派大星普通 2022年10月29日下午4:27

class Solution {
//判断二叉树是否平衡，先算出他的左高度和右高度，再用递归的思想，判断他的左子树和右子树是否平衡，不平衡直接返回，
//平衡时，判断左高度和右高度的大小差，该节点是否平衡
//时间复杂度O(n^2)
//空间复杂度O(n^2)
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        int left = depth(root.left);
        int right = depth(root.right);
        Boolean l = isBalanced(root.left);
        if(l==false)return l;
        Boolean r = isBalanced(root.right);
        if(r==false)return r;
        return (left-right<=1&&right-left<=1?true:false);

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

        return (left>=right?left+1:right+1);
    }
}

0 赞同 0 条回复

@ 普通 2022年10月29日下午4:02

思路:利用上一道题实现的方法即可解决这一道题
时间复杂度：O(n)
空间复杂度：O(n)

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

    }

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

        int rl = maxDepth(root.left) + 1;
        int rr = maxDepth(root.right) + 1;

        if(rl == 0 || rr == 0) return-1;

        if(Math.abs(rl - rr) > 1)
            return -1;

        return rl >= rr ? rl : rr;

    }
}

0 赞同 0 条回复

鸿渐普通 2022年10月29日上午10:03

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

        //自上向下的去判断
        if(Math.abs(maxDepth(root.left)-maxDepth(root.right))<=1){
            return isBalanced(root.right)&&isBalanced(root.left);
        }
        return false;
    }

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

0 赞同 0 条回复

Gg 普通 2022年10月29日上午12:27

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

    // 递归函数计算最大深度，左右子节点深度差大于1返回-1
    public int getDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftLen = getDepth(root.left);
        if(leftLen == -1){
            return -1;
        }
        int rightLen = getDepth(root.right);
        if(rightLen == -1){
            return -1;
        }
        if(Math.abs(leftLen-rightLen) > 1){
            return -1;
        }
        return Math.max(leftLen,rightLen) + 1;
    }
}

0 赞同 0 条回复

狗蛋儿普通 2022年10月28日下午10:12

class Solution {
public:
    //平衡二叉树求高度差不大于1，一定使用的是后序遍历
    //后序遍历一定都是根据返回值进行判断
    //返回值有两层含义，若在本节点之下是平衡二叉树，则返回值为当前节点下最大高度
    //若本节点之下不是平衡二叉树,则返回值为-1,代表并非是平衡二叉树
    int  isBal(TreeNode* pRoot){
        if(pRoot == nullptr) return 0;
        int leftHeight = isBal(pRoot->left);
        if(leftHeight == -1) return -1;
        int rightHeight = isBal(pRoot->right);
        if(rightHeight == -1) return -1;
        if(abs(rightHeight - leftHeight) > 1) return -1;
        else return 1+max(rightHeight,leftHeight);
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(pRoot == nullptr) return true;
        return isBal(pRoot) > 0? true:false;
    }
};

0 赞同 0 条回复

单个酒窝儿普通 2022年10月28日下午8:48

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

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

    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(abs(left - right) > 1) return -1;

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

1 赞同 1 条回复

狗蛋儿普通 @ 单个酒窝儿 2022年10月28日下午10:14

看这个代码风格，看来都是一个老师出来的，哈哈哈

登录以回复

Haoyun 普通 2022年10月28日下午6:57

var isBalanced = function(root) {
  const getDepth = function(root) {
      if(!root) return null;
      let leftHeight = getDepth(root.left);
      let rightHeight = getDepth(root.right)
      if(leftHeight==-1 || rightHeight==-1){
          return -1;
      }
      if(Math.abs(leftHeight-rightHeight)>1) {
          return -1;
      } else {
          return 1+Math.max(leftHeight,rightHeight)
      }
  }
  return !(getDepth(root) === -1);
};

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

1 赞同 0 条回复

T 普通 2022年10月28日下午5:12

class Solution {
    public boolean isBalanced(TreeNode root) {
        return recursion(root) != -1;
    }

    //递归判断
    public int recursion(TreeNode root) {
        if(root == null)
            return 0;
        int left = recursion(root.left);
        // 把-1返回到最外层。
        if(left == -1)
            return -1;
        int right = recursion(root.right);
        if(right == -1)
            return -1;
        //如果该节点左右高度差值大于1，说明不平衡，返回-1。
        if(Math.abs(left - right) > 1)
            return -1;
        return Math.max(left, right) + 1;
    }
}

0 赞同 0 条回复

mpweixin用户永久会员 2022年10月28日下午4:42

class Solution {
    public boolean isBalanced(TreeNode root) {

        if (root == null) return true;
        else {
            return Math.abs(Deepth(root.left) - Deepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }
        public int Deepth(TreeNode root){
          if(root == null) return 0;
          int leftDeepth = Deepth(root.left);
          int rightDeepth = Deepth(root.right);
          return Math.max(leftDeepth,rightDeepth)+1;
       }
}

还是递归，我有想到，但也发现了一些错误

0 赞同 0 条回复

虾仁猪心普通 2022年10月28日下午3:59

平衡二叉树的左子树与右子树深度差不超过1。

class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    private 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 条回复

庄重普通 2022年10月28日下午3:39

//  思路：
//     1.函数功能：判断是否为平衡二叉树，根节点满足并且它的左右子树也需要满足
//     2.关系式bool ret = abs(lDepth - rDepth) <= 1 && isBalanced(root->left) && isBalanced(root->right)
//     3.初始值：root == NULL --> return true;
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root == NULL) return true;

        int lDepth = maxDepth(root->left);
        int rDepth = maxDepth(root->right);

        return abs(lDepth - rDepth) <= 1 && isBalanced(root->left) && isBalanced(root->right);

    }

    int maxDepth(TreeNode* root) {
        if(root == NULL) return 0;

        int lDepth = maxDepth(root->left);
        int rDepth = maxDepth(root->right);

        return max(lDepth,rDepth) + 1;
    }    
};
//时间复杂度：O(nlogn)
//空间复杂度：O(n)

//  优化思路：
//      在判断深度的时候直接检测它是否是平衡二叉树

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root == NULL) return true;

        if(maxDepth(root) == -1) return false;

        return true;

    }
    
    int maxDepth(TreeNode* root) {
        if(root == NULL) return 0;
        
        int lDepth = maxDepth(root->left);
        if(lDepth == -1) return -1;
        int rDepth = maxDepth(root->right);
        if(rDepth == -1) return -1;
        if(abs(lDepth - rDepth) > 1) return -1;

        return max(lDepth,rDepth) + 1;
    }    
};
//时间复杂度：O(n)
//空间复杂度：O(n)

0 赞同 0 条回复

你有点可爱喔普通 2022年10月28日下午3:14

时间复杂度：O(n)
空间复杂度：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) {
    // 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
        if(root==null)return true;
        if(maxDepth(root) == -1)return false;
        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);
         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 条回复

wxc 普通 2022年10月28日下午1:05

额外

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def deep (root:TreeNode) -> int:
            if root is None:
                return 0
            else:
                l = deep(root.left)
                r = deep(root.right)
                return max(l,r) + 1
        if not root :
            return True
        else:
            return abs(deep(root.left) - deep(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

0 赞同 0 条回复

追普通 2022年10月28日上午10:18

class Solution {
public:
    int height(TreeNode* root){
        return root ? max(height(root->left), height(root->right)) +1 : 0;
    }

    bool isBalanced(TreeNode* root) {
        if(root == nullptr) {
            return true;
        }else{
            return abs(height(root->right) - height(root->left)) <= 1 && isBalanced(root->left) &&isBalanced(root->right);  //如果该节点以及两个子节点都为平衡节点，则为二叉树
        }
    }
};

深度优先搜索，自顶向上递归

0 赞同 0 条回复

是梦终空永久会员 2022年10月28日上午8:29

深度搜索，判断左右子树高度，
时间O(n)
空间0(n)

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getdeep(root) != -1;
    }
    public int getdeep(TreeNode root){
        if(root == null)    return 0;
        int left = getdeep(root.left);
        if(left == -1)  return -1;

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

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

0 赞同 0 条回复

黎昕普通 2022年10月28日上午12:52

深搜

O(n)
O(n)

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

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

0 赞同 0 条回复

yanshuojune 普通 2022年10月28日上午12:24

解题方法：对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 -1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。
时间复杂度：O(n)
空间复杂度：O(n)

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        # 自底向上递归
        def depth(root):
            if not root:
                return 0
            ldepth = depth(root.left)
            rdepth = depth(root.right)
            if ldepth == -1 or rdepth == -1 or abs(rdepth-ldepth) > 1:
                return -1
            else:
                return max(rdepth,ldepth) + 1
        return depth(root) >= 0

0 赞同 0 条回复

浅夏的无奈普通 2022年10月28日上午12:09

//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
    public boolean isBalanced(TreeNode root) {
        return res(root)>=0;
    }
    public int res(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftMax = res(root.left);
        int rightMax = res(root.right);
         if (leftMax == -1 || rightMax== -1 || Math.abs(leftMax - rightMax)>1) {
            return -1;
        } else {
            return Math.max(leftMax, rightMax) + 1;
        }
    }
}

0 赞同 0 条回复

Tolkien 永久会员 2022年10月27日下午11:30

**
     * 方法一：先序遍历
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(n)
     */
    public boolean isBalanced(TreeNode root) {
        // 1. 递归结束条件
        if (root == null) {
            return true;
        }

        // 2. 等价关系式
        // 即分析 子树应满足什么情况时，其父为平衡二叉树
        // 条件1 左右子树的深度相差不超过1
        if (Math.abs(maxDepth(root.left) - maxDepth(root.right)) > 1) {
            return false;
        }
        // 条件2 左右子树均为平衡二叉树
        if (!isBalanced(root.left) || !isBalanced(root.right)) {
            return false;
        }
        return true;
    }

    public int maxDepth(TreeNode root) {
        // 1. 结束条件
        if (root == null) {
            return 0;
        }

        // 2. 等价关系式
        return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
    }

    /**
     * 方法二：剪枝
     * 发现方法一大量重复计算树的高度
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public boolean isBalanced2(TreeNode root) {
        // 1. 结束条件
        if (root == null) {
            return true;
        }

        // 2. 等价关系式
        // 即分析 子树应满足什么情况时，其父为平衡二叉树
        if (maxDepth2(root) == -1) {
            return false;
        }
        return true;
    }

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

        // 2. 判断是否需要剪枝
        int leftDepth = maxDepth2(root.left);
        if (leftDepth == -1) {
            return -1;
        }
        int rightDepth = maxDepth2(root.right);
        if (rightDepth == -1) {
            return -1;
        }

        // 1. 剪枝
        if (Math.abs(leftDepth-rightDepth) >= 2) {
            return -1;
        }

        return Math.max(leftDepth, rightDepth)+1;
    }

0 赞同 0 条回复

青木普通 2022年10月27日下午11:18

// 没考虑到节点为空的情况，停了好久T T
// 时间复杂度O(n^2)
// 空间复杂度O(n)
class Solution {
    public int treeHeight(TreeNode node){
            if(node == null){
                return 0;
            }
            return Math.max(treeHeight(node.left), treeHeight(node.right)) + 1;
        }

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

        if(Math.abs(treeHeight(root.left) - treeHeight(root.right)) > 1){
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }
}

// 官解还有自底向上，没想到这个，还得多练练
// 时间复杂度O(n)
// 空间复杂度O(n)
class Solution {
    public int treeHeight(TreeNode node){
        if(node == null){
            return 0;
        }
        int left = treeHeight(node.left);
        int right = treeHeight(node.right);
        if(left==-1 || right==-1 || Math.abs(left-right)>1) return -1;
        return Math.max(left, right) + 1;
    }

    public boolean isBalanced(TreeNode root) {
        return treeHeight(root)>=0; 
    }
}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年10月27日下午11:05

递归

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

/*
时间复杂度o(N) ：N为树的节点数，最差情况下需要遍历树的所有节点
空间复杂度O(N):最差情况下(树退化为链表时)，系统递归需要使用O(N)的栈空间
*/
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        if(maxDepth(root) == -1) return false;
        return true;
    }
    //设置-1表示不是平衡树
    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^2)，其中 n 是二叉树中的节点个数。
最坏情况下，二叉树是满二叉树，需要遍历二叉树中的所有节点，时间复杂度是 O(n)。
对于节点p，如果它的高度是d，则height(p) 最多会被调用 dd 次（即遍历到它的每一个祖先节点时）。对于平均的情况，一棵树的高度h满足O(h)=O(logn)，因为d≤h，所以总时间复杂度为O(nlogn)。对于最坏的情况，二叉树形成链式结构，高度为 O(n)，此时总时间复杂度为 O(n^2)
空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n。
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        return Math.abs(maxDepth(root.left)-maxDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
    //设置-1表示不是平衡树
    public int maxDepth(TreeNode root){
        if(root == null) return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
    }
}

0 赞同 0 条回复

Error 普通 2022年10月27日下午10:58

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if not root:
            return True

        return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

    def depth(self, root: TreeNode):
        if not root:
            return 0

        return max(self.depth(root.left), self.depth(root.right)) + 1

计算两边子树的高度
时间复杂度 O(n)

0 赞同 0 条回复

绍熙普通 2022年10月27日下午9:53

思路：后序遍历 + 剪枝（从底至顶）

class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    private 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 条回复

西西弗斯的石头永久会员 2022年10月27日下午9:24

时间复杂度O（n），空间复杂度O（lgn）。

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        int depth = 0;
        int result = dfs(root);
        if(result == -1){
            return false;
        }
        return true;
    }
    int dfs(TreeNode root){
        if(root == null){
            return 0;
        }

        int left = dfs(root.left);
        if(left == -1) return -1;
        int right=dfs(root.right);
        if(right == -1) return -1;
        if(Math.abs(left-right)>1){
            return -1;
        }
        return Math.max(left,right)+1;
    }
}

0 赞同 0 条回复

So 普通 2022年10月27日下午8:50

/**
 * 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;
        }
        return Math.max(left, right) + 1;
    }
}

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

0 赞同 0 条回复

波波_1936 普通 2022年10月27日下午8:20

 public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        int lHeight = treeHeight(root.left);
        int rHeight = treeHeight(root.right);
        if(Math.abs(lHeight - rHeight) > 1){
            return false;
        }
        return isBalanced(root.left)&&isBalanced(root.right);
    }

    public int treeHeight(TreeNode root) {
        if (root == null) return 0;
        return Math.max(treeHeight(root.left), treeHeight(root.right)) + 1;
    }
    //递归写法
    //时间复杂度O(n平方)/n是二叉树节点，最坏情况下，二叉树成一条线，此时高度为n 需要遍历n次
    //空间复杂度O(n)

0 赞同 0 条回复

Whatever 永久会员 2022年10月27日下午8:18

延用递归的思路，注意点是利用后序遍历计算左右子树最大深度的差值判断是否 > 1。时间O(n) 空间O(n)

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

0 赞同 0 条回复

易水寒永久会员 2022年10月27日下午8:08

//递归

class Solution {
    public boolean isBalanced(TreeNode root) {
        return !(maxDepth(root) == -1);
    }
    private int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int l = maxDepth(root.left);
        int r = maxDepth(root.right);
        if(l == -1 || r == -1 || Math.abs(l-r) > 1) {
            return -1;
        }
        return l > r ? l+1 : r+1;
    }
}

0 赞同 0 条回复

just 普通 2022年10月27日下午8:00

//递归写法
class Solution {
public:
int fun(TreeNode* root){
if(!root) return 0;
int l=fun(root->left);
int r=fun(root->right);
if(l-1 || r-1) return -1;
if(abs(l-r)>1) return -1;
return 1+max(l,r);
}
bool isBalanced(TreeNode* root) {
if(!root) return true;
return fun(root)-1? false:true;
}
};

0 赞同 0 条回复

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

共以下 56 个回答

O(N^2) 递归

O(N) 记忆化搜索，不过优化表现并不好

O(N) 递归求高度的同时判断是否平衡，不平衡就使用特殊量返回（-1）

# 回答此问题取消回复

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

共以下 56 个回答

O(N^2) 递归

O(N) 记忆化搜索，不过优化表现并不好

O(N) 递归 求高度的同时判断是否平衡，不平衡就使用特殊量返回（-1）

# 回答此问题 取消回复

O(N) 递归求高度的同时判断是否平衡，不平衡就使用特殊量返回（-1）

# 回答此问题取消回复