首页 > 试题广场 >

判断是不是平衡二叉树

[编程题]判断是不是平衡二叉树

热度指数：544407 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

样例解释：

样例二叉树如图，为一颗平衡二叉树

注：我们约定空树是平衡二叉树。

数据范围： $n \le 100$ ,树上节点的val值满足 $0 \le n \le 1000$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

输入描述:

输入一棵二叉树的根节点

输出描述:

输出一个布尔类型的值

示例1

输入

{1,2,3,4,5,6,7}

输出

true

示例2

输入

{}

输出

true

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

查看答案及解析

Python 3

Adam_Sun

from functools import lru_cache
class Solution:
    @lru_cache
    def getDepth(self, root: TreeNode) -> int:
        if not root: return 0
        return max(self.getDepth(root.left), self.getDepth(root.right)) + 1

    def IsBalanced_Solution(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_Solution(root.left) and self.IsBalanced_Solution(root.right)

发表于 2024-11-19 14:51:53 回复(0)

Python 3

JianYue

class Solution:
    def IsBalanced_Solution(self, pRoot: TreeNode) -> bool:
        if pRoot is None:
            return True
        ret = self.calc_depth(pRoot)
        if ret == -1:
            return False
        else:
            return True

    def calc_depth(self, root: TreeNode) -> int:
        left, right = 0, 0
        depth = 1
        ln, rn = root.left, root.right
        if ln is None and rn is None:
            return depth
        if ln:
            left = self.calc_depth(ln)
        if rn:
            right = self.calc_depth(rn)
        if left == -1&nbs***bsp;right == -1:
            return -1
        if abs(left - right) > 1:
            return -1
        return max(left, right) + depth

发表于 2022-09-12 22:06:51 回复(0)

Python 3

蓝鲸与风

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return bool布尔型
#
class Solution:
    res=True
    def IsBalanced_Solution(self , root: TreeNode) -> bool:
        # write code here
        def dfs(root: TreeNode):
            if not root:
                return 0
            if abs(dfs(root.left)-dfs(root.right))>1:
                self.res=False#需要加self
            return max(dfs(root.left),dfs(root.right))+1
        dfs(root)
        return self.res

发表于 2022-08-19 19:11:18 回复(0)

Python 3

在研究求职打法的香菇

class Solution:
    res = 0
    def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
        # write code here
        if pRoot == None:
            return True
        self.deep(pRoot)
        if self.res > 1:
            return False
        else:
            return True
        
    def deep(self, root):    # 当前节点的最大深度
        if root == None:
            return 0
        l = self.deep(root.left)
        r = self.deep(root.right)
        self.res = max(abs(l-r), self.res)    # 记录最大深度差
        return max(l, r) + 1

直接计算子树的高度差并记录最大高度差，高度的计算完全跟 BM28一样

发表于 2022-07-29 20:19:54 回复(0)

Python 3

牛客902478625号

def check(node):
    if node is None:
        return 0, True
    
    # 不是叶节点
    if node.left&nbs***bsp;node.right:
        h1, res1 = check(node.left)
        h2, res2 = check(node.right)
        height = max(h1, h2) + 1
        if abs(h1-h2)<=1 and res1 and res2:
            res = True
        else:
            res = False
        return height, res
    # 叶节点
    else:    
        return 1, True

    
class Solution:
    def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
        # write code here
        return check(pRoot)[1]

O(n)复杂度，同时做计算深度和判断是否平衡

发表于 2022-06-26 14:49:18 回复(0)

Python 3

Vivimore

平衡二叉树：左右子树的高度差绝对值不超过1且左右子树都是平衡二叉树

class Solution:
    def depth(self, root):
        if not root:
            return 0
        ldep = self.depth(root.left)
        if ldep == -1:
            return -1
        rdep = self.depth(root.right)
        if rdep == -1:
            return -1
        sub = abs(ldep - rdep)
        if sub > 1:
            return -1
        return max(ldep, rdep) + 1
    def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
        return self.depth(pRoot) != -1

发表于 2022-05-17 11:54:01 回复(0)

Python 3

宫城良田z

'''
思路: 两次递归，
1)计算根节点左右子树的最大深度;
2)依次遍历节点, 将节点作为根结点计算左右子树的最大深度.
'''
class Solution:
    def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
        # write code here
        def _cal_depth(node):
            if node == None: return 0

            def _dfs(node, cur_depth, max_depth):
                if node == None: return
                max_depth[0] = max(cur_depth, max_depth[0])
                _dfs(node.left, cur_depth + 1, max_depth)
                _dfs(node.right, cur_depth + 1, max_depth)
                return max_depth[0]

            return _dfs(node, 1, [1])

        def dfs(node, sign):
            if node == None:
                return
            L = _cal_depth(node.left)
            R = _cal_depth(node.right)
            if abs(L - R) > 1:
                sign[0] = False
            dfs(node.left, sign)
            dfs(node.right, sign)

        sign = [True]
        dfs(pRoot, sign)
        return sign[0]

发表于 2022-04-19 22:05:06 回复(0)

Python 3

想搞机器学习的小白

常规两种解法，其中BFS时间复杂度为o(n^2)

class Solution:
    def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
        # write code here
        #BFS
#         def depth(root):
#             if not root:return 0
#             return 1+max(depth(root.left),depth(root.right))
#         def bfs(root):
#             if not root:return True
#             left = depth(root.left)
#             right = depth(root.right)
#             return abs(left -right)<=1 and bfs(root.left) and bfs(root.right)
#         return bfs(pRoot)
#         #DFS
#         self.res=True
#         def dfs(root):
#             if not root:return 0
#             left = dfs(root.left)
#             right = dfs(root.right)
#             if abs(left-right)>1:
#                 self.res=False
#             return 1+max(left,right)
#         dfs(pRoot)
#         return self.res

发表于 2022-04-12 15:34:25 回复(0)

Python 3

Yyyzs

class Solution:
    """
    递归法与迭代法：
    """
    def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
        # write code here
        
        if pRoot == None:
            return True
        
        res = self.mySolution2(pRoot)
        
        return res
    
    def mySolution2(self, pRoot):
        # 迭代
        def getMaxDepth(node):  # 得到最大深度就是高度
            stack = []
            depth = 0
            res = 0
            if node:
                stack.append(node)
            while len(stack):
                node = stack.pop()
                if node == None:  
                    node = stack.pop()
                    depth -= 1
                else:
                    stack.append(node)
                    stack.append(None)
                    depth += 1
                    if node.right:
                        stack.append(node.right)
                    if node.left:
                        stack.append(node.left)
                
                res = res if res > depth else depth
            return res
        
        stack = []
        stack.append(pRoot)
        while len(stack):
            node = stack.pop()  
            
            if node == None:
                node = stack.pop()
            else:
                if abs(getMaxDepth(node.left) - getMaxDepth(node.right)) > 1:
                    return False
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
                stack.append(node)
                stack.append(None)
                
        return True
            

    def mySolution(self, pRoot):
        # 递归
        # 通过

        def getHeight(node):
            if node == None:
                return 0
            
            left_height = getHeight(node.left)
            if left_height == -1:
                return -1
            
            right_height = getHeight(node.right)
            if right_height == -1:
                return -1

            if abs(left_height - right_height) > 1:  
                res = -1
            else:
                res =  1 + max(left_height, right_height)
                
            # return -1 if abs(left_height - right_height) > 1 else 1 + max(left_height, right_height)
            
            return res
        
        
        return False if getHeight(pRoot)==-1 else True

发表于 2022-03-07 21:03:33 回复(0)

Python 3

tanx2024

class Solution:
    def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
        # write code here
        if not pRoot: return True
        if self.test(pRoot) == -1: return False
        else: return True
    def test(self, pRoot):
        if not pRoot: return 0
        lh = self.test(pRoot.left)
        if lh == -1: return -1
        rh = self.test(pRoot.right)
        if rh == -1: return -1
        if abs(rh-lh)<=1: return max(lh, rh)+1
        else: return -1

使用一个递归，不用专门计算子树的高度：

1. 当函数返回-1表示当前节点为根节点的树不是平衡二叉树

2. 否则返回函数的高度

发表于 2022-03-05 21:01:25 回复(0)

Python 3

Joy_9

class Solution:
    def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
        if not pRoot:
            return True
        if self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right) and abs(self.depth(pRoot.left)-self.depth(pRoot.right))<=1:
            return True
        else:
            return False

    def depth(self,pRoot):
        if not pRoot:
            return 0
        else:
            return max(self.depth(pRoot.right),self.depth(pRoot.left))+1

发表于 2022-01-09 01:09:27 回复(0)

Python 3

在游泳的芭乐很胖墩墩

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def IsBalanced_Solution(self, pRoot):
        # write code here
        if pRoot is None:
            return True
        elif abs(self.depth(pRoot.left)-self.depth(pRoot.right))<=1:
            return (self.IsBalanced_Solution(pRoot.left) 
                    and  self.IsBalanced_Solution(pRoot.right))
        else:
            return False
    def depth(self, pRoot):
        if pRoot:
            return 1+max(self.depth(pRoot.left),self.depth(pRoot.right))
        else:
            return 0

发表于 2021-09-11 21:20:12 回复(0)

Python 3

阿司匹林Yo

class Solution:
    # 计算左右子树长度过程中判断
    def judge(self, res, root):
        if not root:
            return 0
        l = self.judge(res, root.left)
        r = self.judge(res, root.right)
        if abs(r-l) > 1:
            res[0] = False
        return max(l, r)+1

    def IsBalanced_Solution(self, pRoot):
        if not pRoot:
            return True
        res = [True]
        self.judge(res, pRoot)
        return res[0]

发表于 2021-08-30 22:45:36 回复(0)

Python 3

牛客38477449号

class Solution:
    def IsBalanced_Solution(self, pRoot):
        # write code here
        if not pRoot:
            return True
        
        def dfs(root):
            if not root:
                return Info(True, 0)
            left = dfs(root.left)
            right = dfs(root.right)
            return Info(left.isBBT and right.isBBT and abs(left.height - right.height) <= 1, max(left.height+1, right.height+1))
        
        return dfs(pRoot).isBBT

class Info:
    def __init__(self, isBBT, height):
        self.isBBT = isBBT
        self.height = height

发表于 2021-08-30 18:47:37 回复(0)

Python 3

tantantansq

class Solution:
    def depth(self,pRoot):
        if pRoot==None:
            return 0
        return 1+max(self.depth(pRoot.left),self.depth(pRoot.right)) 
        
    def IsBalanced_Solution(self, pRoot):
        # write code here
        if pRoot==None:
            return True
        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right) and abs(self.depth(pRoot.left)-self.depth(pRoot.right))<=1

发表于 2021-08-05 16:58:09 回复(0)

Python 3

牛客35961088号

def order(root):
    if not root:
        return True, 0
    left, dl = order(root.left)
    right, dr = order(root.right)
    if left and right and abs(dl-dr)<=1:
        return True, max(dl, dr) + 1
    else:
        return False, max(dl, dr) + 1


class Solution:
    def IsBalanced_Solution(self, pRoot):
        # write code here
        a, _ = order(pRoot)
        return a

发表于 2021-07-28 16:22:44 回复(0)

Python 3

611的

class Solution:
    def IsBalanced_Solution(self, pRoot):
        return True if pRoot is None else abs(self.TreeDepth(pRoot.left)-self.TreeDepth(pRoot.right))<=1 and self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
    def TreeDepth(self, pRoot):
        return 0 if pRoot is None else max(1+self.TreeDepth(pRoot.left),1+self.TreeDepth(pRoot.right))

发表于 2021-07-25 19:55:11 回复(0)

提交观点

问题信息

树 dfs

难度：

20条回答 3029收藏 114000浏览

通过挑战的用户

查看代码

松林子木

2023-03-08 10:11:58
K乀

2023-03-04 18:40:08
已注销

2023-02-27 09:59:55
Elastic...

2023-02-26 10:54:43
随机昵称都有什...

2023-02-23 15:17:28

判断是不是平衡二叉树

输入描述:

输出描述:

输入

输出

输入

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题