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

LovLe 普通 2024年12月21日上午9:33

自顶向下

# 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 depth(self,root):   #计算出子树高度
        if not root: return 0
        return max(self.depth(root.left),self.depth(root.right))+1
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if not root: return True
        # ld=self.depth(root.left)
        # rd=self.depth(root.right)
        # if not (ld-rd<=1 or rd-ld<=1):    #有测试用例不通过？
        #     return False
        return abs(self.depth(root.left)-self.depth(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)              #保证左右子树的高度差不大于1，继续遍历左右子树是否为二叉平衡树

自底向上，剪枝

# 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 depth(self,root):
        if not root: return 0
        ld=self.depth(root.left)
        rd=self.depth(root.right)
        if abs(ld-rd)>1:    #左右子树深度>1，剪枝，直接返回-1
            return -1
        return max(ld,rd)+1 #计算左右子树的深度
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if not root: return True
        if self.depth(root)==-1: return False   # 直接返回
        return  self.isBalanced(root.left) and self.isBalanced(root.right)     #继续判断左右子树

0 赞同 0 条回复

yelinliner 普通 2024年12月16日下午4:16

第一种

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

    // 二叉树的深度
    public int calculateDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = calculateDepth(root.left);
        int right = calculateDepth(root.right);
        return Math.max(left, right) + 1;
    }
}
// 时间复杂度是O(nlogn),空间是O(n)

第二种

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

    }

    // 二叉树的深度
    public int calculateDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = calculateDepth(root.left);
        if (left == -1)
            return -1;
        int right = calculateDepth(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用户普通 2024年12月14日下午3:54

递归：时间O(N), 空间O(N)

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root == NULL) return true;
        int left = calculateDepth(root->left);
        if( left == -1) return false;
        int right =calculateDepth(root->right);
        if( right == -1) return false;
        return abs(left-right) <= 1 ? true : false;
    }

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

0 赞同 0 条回复

岱永久会员 2024年12月11日下午3:03

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right; 
 *     }
 * }
 */
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;
    }
}

先序遍历 + 判断深度（从顶至底）

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

晓宇普通 2024年12月5日下午3:53

// 优化
class Solution {
public:
    // 思路：在搜索高度的时候，判断该节点左右子树的高度差是否小于1
    int depth(TreeNode* root){
        if(!root) return 0;
        int l = depth(root->left);
        if(l == -1) return -1;
        int r = depth(root->right);
        if(r == -1) return -1;
        if(abs(l - r) > 1) return -1;         // 优化
        return max(l, r) + 1;
    }

    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        if(depth(root) == -1) return false;
        return true;

    }
    // 时间复杂度:o(n); 空间复杂度:o(n)

};

0 赞同 0 条回复

mpweixin用户普通 2024年12月5日上午12:58

递归

# 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:
        if not root:
            return True
        def recur(root):
            if not root:
                return 0
            left = recur(root.left)
            if left == -1:
                return -1
            right = recur(root.right)
            if right == -1:
                return -1
            if abs(left - right) > 1:
                return -1
            return max(left, right) + 1
        result = recur(root)
        return result != -1

0 赞同 0 条回复

🌟 普通 2024年12月3日下午8:00

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

};

0 赞同 0 条回复

Jerry 普通 2024年12月1日下午9:59

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        int leftdepth = getDepth(root->left);
        int rightdepth = getDepth(root->right);
        if(abs(leftdepth - rightdepth) > 1) return false;
        return isBalanced(root->left)&&isBalanced(root->right);
    }
    int getDepth(TreeNode* root){
        if(!root) return 0;
        if(!root->left && !root->right) return 1;
        queue<TreeNode*> q;
        int depth = 0;
        q.push(root);
        while(!q.empty()){
            depth++;
            int sz = q.size();
            for(int i = 0; i < sz; i++){
                TreeNode* tmp = q.front();
                q.pop();
                if(tmp->left) q.push(tmp->left);
                if(tmp->right) q.push(tmp->right);
            }
        }
        return depth;
    }
};

这个时间复杂度是？

0 赞同 0 条回复

陆狗陆狗普通 2024年12月1日下午2:47

题解

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        // 左右子树的高度差<=1
        int leftDepth=calculateDepth(root.left);
        int rigthDepth=calculateDepth(root.right);
        if(Math.abs(leftDepth-rigthDepth)<=1){
            // 左右子树都是平衡二叉树
            return isBalanced(root.left)&&isBalanced(root.right);
        }else{
            return false;
        }
    }

    // 计算二叉树的深度
    public int calculateDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        return Math.max(calculateDepth(root.left),calculateDepth(root.right)) + 1;
    }
}

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日下午5:40

/**
方法一：自顶向下
每个节点都获取左右子树高度，判断是否为平衡二叉树，在递归判断左右子树是否平衡，由于每个节点都要计算一次树的高度，时间复杂度O(N**2)

方法二：自低向上
基于后序遍历的思路（左右根），左右子树高度优先于当前节点树高度计算出来，高度自低向上传递，若子树左右高度差>1，
则置高度为-1声明该子树不平衡，时间复杂度O(N)
 */
class Solution {

    // 方法一
    // public boolean isBalanced(TreeNode root) {
    //     if (root == null){
    //         return true;
    //     }
    //     int dif = Math.abs(getHeight(root.left) -  getHeight(root.right));
    //     return dif <= 1 && isBalanced(root.left) && isBalanced(root.right);


    // }

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


    /// 方法二

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

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

0 赞同 0 条回复

Tom Yuan 普通 2024年11月30日上午8:33

方法递归但是加一下记忆的方式来减少重复计算的次数，子树如果已经判断不平衡则直接return -1

class Solution:
    def calculateDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0

        left = self.calculateDepth(root.left)
        if left == -1:
            return -1
        right = self.calculateDepth(root.right)
        if right == -1:
            return -1

        if abs(left - right) > 1:
            return -1
        # remember to +1 so that the value can increase.
        return max(left, right) + 1

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        if self.calculateDepth(root) == -1:
            return False

        return True

time O(n) space O(n)

0 赞同 0 条回复

Renasc 普通 2024年11月28日下午10:05

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

class Solution {
    public boolean isBalanced(TreeNode root) {
        // 如果为空，则为平衡二叉树
        if (root == null) {
            return true;
        } else {
            // 否则需要满足二叉平衡树的条件
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

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

}

0 赞同 0 条回复

jaron 普通 2024年11月28日上午9:50

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

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

    public int f(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = f(root.left);
        int right = f(root.right);
        // 只要有不平衡的直接返回-1，避免重复计算
        if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }
        return Math.max(left, right) + 1;
    }
}

0 赞同 0 条回复

🍊 普通 2024年11月27日下午11:30

递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int Depth(TreeNode root){
if(root null) return 0;
return 1 + Math.max(Depth(root.left), Depth(root.right));
}

public boolean isBalanced(TreeNode root) {
    if(root == null) return true;
    int l = Depth(root.left), r = Depth(root.right);
    if(Math.abs(l - r) >= 2) return false;
    return isBalanced(root.left) && isBalanced(root.right);
}

}

0 赞同 0 条回复

黑键〰普通 2024年11月27日下午10:32

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    let flag = true
    const maxDepth = (root) => {
        if(root == null) return 0
        let left = maxDepth(root.left)
        let right = maxDepth(root.right)
        if(Math.abs(left - right) > 1) {
            flag = false
        }
        return Math.max(left, right) + 1
    }
    maxDepth(root)
    return flag
};

思路：学习题解里别人的解法。主体是以上一题的计算深度为主，然后计算过程中通过后续遍历一次次比较左右树深度差是否大于1

0 赞同 0 条回复

休一普通 2024年11月27日下午8:54

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return dfs(root)==-1?false:true;
    }
    int dfs(TreeNode* root)
    {
        //如果到达叶子节点，深度+0
        if(root==nullptr) return 0;
        //左子树向下递归
        int leftDepth = dfs(root->left);
        if(leftDepth==-1) return -1;
        //右子树向下递归
        int rightDepth = dfs(root->right);
        if(rightDepth==-1) return -1;
        //子树判断是否为平衡二叉树
        return abs(leftDepth-rightDepth)>1?-1:max(leftDepth,rightDepth)+1;
    }
};
//时间复杂度o(N)
//空间复杂度o(N)

0 赞同 0 条回复

Kisara 普通 2024年11月27日下午8:22

先实现深度计算，然后判断深度是否差1以上
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        return preOrder(root);
    }

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

        int leftDepth=depth(root.left)+1;
        int rightDepth=depth(root.right)+1;

        return Math.max(leftDepth,rightDepth);
    }

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

        if(Math.abs(depth(root.left)-depth(root.right))>=2) return false;
        boolean r1= preOrder(root.left);
        boolean r2=preOrder(root.right);

        return r1&&r2;
    }
}

时间on 空间on

0 赞同 0 条回复

无言永久会员 2024年11月27日下午5:26

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;
        } else {
            return max(leftHeight, rightHeight) + 1;
        }
    }
    bool isBalanced(TreeNode* root) {
        return height(root) != -1;
    }
};
时间复杂度：O(n) 
空间复杂度：O(n)

0 赞同 0 条回复

秋山丽奈普通 2024年11月27日下午4:58

思路：计算当前结点字数深度并判断是否满足

class Solution {
    public boolean isBalanced(TreeNode root) {
        return check(root);
    }

    boolean check(TreeNode node){
        if(node == null){
            return true;
        }

        int leftDepth = getDepth(node.left);
        int rightDepth = getDepth(node.right);

        if(Math.abs(leftDepth - rightDepth) > 1){
            return false;
        }

        return check(node.right) && check(node.left);
    }

    int getDepth(TreeNode node){
        if(node == null){
            return 0;
        }

        int leftDepth = getDepth(node.left);
        int rightDepth = getDepth(node.right);

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

0 赞同 0 条回复

月下足迹普通 2024年11月27日下午4:05

//时间复杂度O(N2),空间复杂度为O(N)

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

}


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

    int leftHeight = checkBalance(root.left);
    if (leftHeight == -1) {
        return -1;
    }

    int rightHeight = checkBalance(root.right);
    if (rightHeight == -1) {
        return -1;
    }

    if (Math.abs(leftHeight - rightHeight) > 1) {
        return -1;
    }

    return Math.max(leftHeight, rightHeight) + 1;
}

0 赞同 0 条回复

Aatorx 永久会员 2024年11月27日下午3:15

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

思路为递归判断二叉树的各个子树是否为平衡二叉树
时间复杂度为O(NlogN)，递归判断子树是否是平衡二叉树时间复杂度为O(logN)，递归返回二叉树的最大深度时间复杂度为O(N)。
空间复杂度为O(N)。

0 赞同 0 条回复

迢迢星野普通 2024年11月27日上午10:36

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);
        return getHeight(root) != -1;
    }

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

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

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

    private int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }

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

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

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

思路：两种方法，都是利用递归的方式，一种是检查以当前节点为根节点的二叉树是否是平衡二叉树，并递归的检查其左右子树是否平衡；另一种就是在计算每个节点其左右子树的最大深度的过程中判断是否满足平衡二叉树的要求。
时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

lQl 永久会员 2024年11月27日上午9:56

递归后序遍历+剪枝
时间复杂度O(n)
空间复杂度O(n)

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

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

0 赞同 0 条回复

苯庸普通 2024年11月27日上午9:46

class Solution {
public boolean isBalanced(TreeNode root) {
if(root null){
return true;
}
if(Math.abs(getDepth(root.left) – getDepth(root.right)) > 1){
return false;
}
return isBalanced(root.left) && isBalanced(root.right);

}

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

}
时间：O（n）
空间：O（n）

0 赞同 0 条回复

youngsir 普通 2024年11月27日上午9:38

打卡，先递归求深度，再利用性质。

/**
 * 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:
    bool isBalanced(TreeNode* root) {
       if(root == nullptr){
            return true;
       }
       int leftDep = depth(root->left);
       int rightDep = depth(root->right);
       return isBalanced(root->left) && isBalanced(root->right) && abs(leftDep-rightDep)<=1;
    }
    int depth(TreeNode* root){
        if(root == nullptr){
            return 0;
        }
        int leftDepth = depth(root->left);
        int rightDepth = depth(root->right);
        int maxdepth = 1+ max(leftDepth,rightDepth);
        return maxdepth;

    }

};

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

0 赞同 0 条回复

Xiang. 永久会员 2024年11月27日上午9:37

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

    public int calculateDepth(TreeNode root) {
        if (root == null)
            return 0;
        return Math.max(calculateDepth(root.left) + 1, calculateDepth(root.right) + 1);
    }
}
思路：采用自顶向下的递归方式，计算根节点及子节点的左右子树深度差的绝对值是否大于1；
时间复杂度o(n²)
空间复杂度o（n）

0 赞同 0 条回复

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

共以下 26 个回答

自顶向下

自底向上，剪枝

# 回答此问题取消回复

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

共以下 26 个回答

自顶向下

自底向上，剪枝

# 回答此问题 取消回复

# 回答此问题取消回复