首页 > 试题广场 >

判断是不是平衡二叉树

[编程题]判断是不是平衡二叉树
  • 热度指数：544019 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
样例解释：
样例二叉树如图，为一颗平衡二叉树
注：我们约定空树是平衡二叉树。

数据范围：,树上节点的val值满足
要求：空间复杂度，时间复杂度

输入描述:
输入一棵二叉树的根节点


输出描述:
输出一个布尔类型的值
示例1

输入

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

输出

true
示例2

输入

{}

输出

true

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Python
LYC_ley头像 LYC_ley 
class Solution:
    def TreeDepth(self, pRoot1):
        # write code here
        if not pRoot1:
            return 0
        left = self.TreeDepth(pRoot1.left)
        right = self.TreeDepth(pRoot1.right)
        return max(left,right)+1
    def IsBalanced_Solution(self, pRoot):
        if not pRoot:
            return True
        Deepl = self.TreeDepth(pRoot.left)
        Deepr = self.TreeDepth(pRoot.right)
        Boolean1 = 0
        if abs(Deepl-Deepr)>1:
            Boolean1 = 0
            return False
        else:
            Boolean1 = 1
        return self.IsBalanced_Solution(pRoot.left)and self.IsBalanced_Solution(pRoot.right)
        
        # write code here
想用递归不过不想在求深度的地方直接判断是否平衡，从题解函数处判断，若不平衡直接跳出false，否则一直执行到None
发表于 2021-08-22 10:42:49 回复(0)
Python
牛客541273514号头像 牛客541273514号 
# -*- 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 not pRoot:
            return True
        if not pRoot.left and not pRoot.right:
            return True
        if not pRoot.left and pRoot.right:
            if self.depth(pRoot.right)<=1:
                return True
            else:return False
        if not pRoot.right and pRoot.left:
            if self.depth(pRoot.left)<=1:
                return True
            else:return False
        if pRoot.left and pRoot.right:
            if self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right):
                if -1<=self.depth(pRoot.left)-self.depth(pRoot.right)<=1:
                    return True
            return False
            
    def depth(self,pRoot):
        if not pRoot:
            return 0
        if not pRoot.left and not pRoot.right:
            return 1
        left=self.depth(pRoot.left)
        right=self.depth(pRoot.right)
        return 1+max(left,right)

发表于 2021-05-02 18:10:21 回复(0)
Python
wengJJ头像 wengJJ
Python
递归法：以小见大，只要小的子树不是平衡二叉树则可判定整个树都不是平衡二叉树 
# -*- 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):
        return self.IsBalanced(pRoot)!=-1
        # write code here
    def IsBalanced(self, pRoot):
        if not pRoot:
            return 0
        left = self.IsBalanced(pRoot.left)
        right = self.IsBalanced(pRoot.right)
        if left>=0 and right>=0 and abs(left-right)<=1:
            return 1+max(left,right)
        else:
            return -1


发表于 2021-04-22 12:33:21 回复(0)
Python
201810061921539头像 201810061921539
python3 dfs剪枝解法 
class Solution:
    def IsBalanced_Solution(self, pRoot):
        if pRoot is None:
            return True
        # write code here
        def dfs(root):
            if not root:
                return 0
            l = dfs(root.left)
            r = dfs(root.right)
            if l is False:
                return l
            if r is False:
                return r
            lh = 1 + l
            rh = 1 + r
            if abs(lh-rh) > 1:
                return False
            return max(lh,rh)
        return dfs(pRoot)



编辑于 2021-03-10 17:14:51 回复(0)
Python
牛客174432419号头像 牛客174432419号
接上一题，先写一个获取二叉树深度的辅助函数def DepthOfTree(self,root)，然后在原函数中进行判定。
附上代码： 
class Solution:
    def DepthOfTree(self,root):
        if root is None:
            return 0
        depth = max(self.DepthOfTree(root.left), self.DepthOfTree(root.right))+1
        return int(depth)
    
    def IsBalanced_Solution(self, pRoot):
        if not pRoot:
            return True
        else:
            left_depth = self.DepthOfTree(pRoot.left)
            right_depth  = self.DepthOfTree(pRoot.right)
            if abs(left_depth-right_depth) <= 1:
                return True
            return False


发表于 2021-03-03 17:17:52 回复(2)
Python
bruceyanwee头像 bruceyanwee 
# 从最底层返回的是深度，但是一旦出现了不平衡False，往上走都是False了，所以
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def dfs(node):
            if node==None:
                return 1
            depth_l = dfs(node.left)
            depth_r = dfs(node.right)
            if not depth_l&nbs***bsp;not depth_r:
                return False
            return 1+max(depth_l,depth_r) if abs(depth_l-depth_r)<2 else False        
        return True if dfs(root) else False

发表于 2020-09-17 23:50:03 回复(0)
Python
火树银花zjl头像 火树银花zjl 
# -*- 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):
        return self.depth(pRoot)!=-1
        # write code here
    def depth(self,root):
        if not root:
            return 0
        l=self.depth(root.left)
        if l==-1:
            return -1
        r=self.depth(root.right)
        if r==-1:
            return -1
        c=abs(l-r)
        if c>1:
            return -1
        return max(l,r)+1

发表于 2020-09-11 11:23:57 回复(0)
Python
DDooo头像 DDooo 
# -*- 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 not pRoot :
            return True
        if abs(self.maxDepth(pRoot.left) - self.maxDepth(pRoot.right))>1:
            return False
        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
    def maxDepth(self, root):
        if root == None:
            return 0
        return max(self.maxDepth(root.left),self.maxDepth(root.right))+1
    

发表于 2020-07-26 16:49:27 回复(0)
Python
吃瓜小丸子头像 吃瓜小丸子
1、首先翻译题意，只判断是否平衡的话，其实就是说对于每一个节点，左子树的最大深度和右子数的最大深度的差的绝对值不大于1。
2、二叉树用递归还是方便，那就记录下每个节点的左右子树的深度然后比较呗。 
class Solution:
    def IsBalanced_Solution(self, pRoot):
        if not pRoot:
            return True
        state, _ = self.get_depth(pRoot, 0)
        return state
    def get_depth(self, pRoot, depth):
        if not pRoot:
            return True, depth
        l_mark, l_depth = self.get_depth(pRoot.left, depth + 1)
        r_mark, r_depth = self.get_depth(pRoot.right, depth + 1)
        if abs(l_depth - r_depth) > 1:
            return False, max(l_depth, r_depth)
        return l_mark and r_mark, max(l_depth, r_depth)


编辑于 2020-06-04 21:59:54 回复(0)
Python
Kuriyamaaa头像 Kuriyamaaa 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        p=pRoot
        if p==None:
            return 0
        if p.left==None and p.right==None:
            return 1

        return max(self.TreeDepth(p.left),self.TreeDepth(p.right))+1
            
    def IsBalanced_Solution(self, pRoot):
        p=pRoot
        re=True
        if not p:
            re=True
            return re
        if abs(self.TreeDepth(p.left)-self.TreeDepth(p.right))>1:
            re=False
            return re
        if p.left!=None and p.right!=None:
            pass
        
        re=re and (self.IsBalanced_Solution(p.left)) and (self.IsBalanced_Solution( p.right))
        return re
        # write code here

发表于 2020-05-29 23:39:43 回复(0)
Python
sky游荡头像 sky游荡 
递归一下：

class Solution:
    def __init__(self):
        self.flag = True    
    def IsBalanced_Solution(self, pRoot):
        self.isb(pRoot)
        return self.flag
    
    def isb(self,pRoot):
        if not pRoot or self.flag ==False :
            return [0,0]
        else:
            lla = self.isb( pRoot.left)
            rra = self.isb( pRoot.right)
            ll = max(lla[0],lla[1])+1
            rr = max(rra[0],rra[1])+1
            if abs(ll-rr)>1:      
                self.flag = False
                return [0,0]                
            return [ll,rr]
        # write code here

      

编辑于 2020-04-02 17:08:22 回复(0)
Python
牛客447097232号头像 牛客447097232号 
# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def __init__(self):
        self.res = True
    def IsBalanced_Solution(self, pRoot):
        self.post_order(pRoot)
        return self.res

    def post_order(self,root):
        if not root:
            return 0
        left = self.post_order(root.left)
        right = self.post_order(root.right)
        if abs(left - right) > 1 :
            self.res = False
        return max(left,right) + 1


t = TreeNode(8)
t.left = TreeNode(6)
t.right = TreeNode(10)
t.left.left = TreeNode(5)
t.left.right = TreeNode(7)
t.right.left = TreeNode(9)
t.right.right = TreeNode(11)
s = Solution()
ans = s.IsBalanced_Solution(t)
print(ans)

发表于 2020-03-03 11:27:07 回复(0)
Python
朝夕_头像 朝夕_ 
class Solution:
    def IsBalanced_Solution(self, pRoot):
        # edge
        if not pRoot:
            return True
        # helper function
        def dfs(root):
            # condition
            if not root:
                return 0
            return 1 + max(dfs(root.left),dfs(root.right))
        # function call
        return abs(dfs(pRoot.left) - dfs(pRoot.right)) <= 1 and self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)


编辑于 2020-03-03 14:10:29 回复(0)
Python
黄沙遮天头像 黄沙遮天 
class Solution:
    def cacluatees(self,root):
        if root==None:
            return 0
        l1=self.cacluatees(root.left)
        l2=self.cacluatees(root.right)
        #如果是非平衡树，就进行计数
        if l1>l2+1&nbs***bsp;l1+1<l2:
            self.flag+=1
        #返回左右子树中最高的那个，加上1作为根的高度
        return (l1+1) if l1>l2 else (l2+1)
    def IsBalanced_Solution(self, pRoot):
        # write code here
        if pRoot==None:
            return True
        self.flag=0
        length1=self.cacluatees(pRoot)
        if self.flag==0:
            return True
        else:
            return False
我们需要做的就是计算左子树的最大高度，和右子树的最大高度，然后进行判断是否是平衡树。
另外对于递归的情况，我们判断某一内节点的左子树和右子树时，我们先判断该内节点是否是平衡二叉树，然后将左右子树中的最大高度加一作为该内节点的深度，然后再回溯判断该内节点的父节点是否是平衡二叉树，并将该内节点和其兄弟节点的最大值加上一赋值给其父节点，作为子树的高度
发表于 2020-01-04 22:24:17 回复(0)
Python
天山剑客头像 天山剑客 
# 解题思路：平衡二叉树三个条件：左右子树都是平衡二叉树，左右子树高度差不超过1
class Solution:
    def IsBalanced_Solution(self, pRoot):
        # write code here
        if not pRoot:
            return True

        def TreeDepth(node):
            if not node:
                return 0
            else:
                return max(TreeDepth(node.left), TreeDepth(node.right)) + 1

        lf = self.IsBalanced_Solution(pRoot.left)
        if not lf:
            return False

        rf = self.IsBalanced_Solution(pRoot.right)
        if not rf:
            return False

        return abs(TreeDepth(pRoot.left) - TreeDepth(pRoot.right)) <= 1
    

发表于 2019-12-05 11:51:43 回复(0)
Python
Kirto先森头像 Kirto先森
python版本
给出了建树函数，大家可以自己在本地调试跟踪函数递归是怎么执行的，加深理解 
class TreeNode:
    def __init__(self,x):
        self.val = x
        self.left = None
        self.right = None
    
class Solution:
    def __init__(self, array):
        self.array = array
        self.length = len(array)
        
    def createTree(self, i):
        left, right = i*2+1, i*2+2
        root = TreeNode(self.array[i])
        if left<self.length:
            if self.array[left]==".":
                root.left = None
            else:
                root.left = self.createTree(left)
        if right<self.length:
            if self.array[right]==".":
                root.right = None
            else:
                root.right = self.createTree(right)
        return root
        
    def IsBalanced_Solution(self, pRoot):
        self.flag = True
        def loop(root):
            if not root:
                return 0
            left = loop(root.left)
            right = loop(root.right)
            if left-right>1 or left-right<-1:
                self.flag = False
            return max(left, right)+1
        
        loop(pRoot)
        return self.flag
        
tmp = Solution(['1','2','3','4','5','.','.','.','.','6'])
root = tmp.createTree(0)
res = tmp.IsBalanced_Solution(root)


发表于 2019-11-19 15:48:17 回复(0)
Python
秋水中的鱼头像 秋水中的鱼
平衡二叉树的定义:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

定义一个类似上一题求二叉树深度的函数,由于平衡二叉树的定义中有一条"左右两个子树都是一棵平衡二叉树",所以当递归到高度差大于1时就返回-1,不用再递归下去浪费时间了 
# -*- 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):
        def get_depth(root):
            if not root:
                return 0
            left=get_depth(root.left)
            right=get_depth(root.right)
            if left==-1 or right==-1:
                return -1
            if abs(left-right)<=1:
                return max(left,right)+1
            else:
                return -1
        if not pRoot:
            return True
        return get_depth(pRoot)!=-1
发表于 2019-11-08 14:15:05 回复(0)
Python
爱吃面包和酸奶的螺丝头像 爱吃面包和酸奶的螺丝

数据结构

栈

解题思路

利用平衡二叉树的定义：左右子树的高度差不超过1，先定义一个求树的深度的函数TreeDepth，然后分别求出左子树和右子树的深度，再把这两个深度相减取绝对值，看是否超过1，没有的话就返回True，否则返回False。树为空时返回True

代码

# -*- 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 not pRoot:
            return True
        if abs(self.TreeDepth(pRoot.left) - self.TreeDepth(pRoot.right)) <= 1:
            return True
        else:
            return False

    def TreeDepth(self, pRoot):
        if not pRoot:
            return 0
        return max(self.TreeDepth(pRoot.left) + 1, self.TreeDepth(pRoot.right) + 1)
发表于 2019-10-28 09:24:59 回复(0)
Python
刀轻城_algo头像 刀轻城_algo 
    # 递归判断
    # 以某节点为根的子树平衡需要：该节点平衡&左子树平衡&右子树平衡
    # 判断平衡需要获得左右子树的高度
    # 该函数在某子树平衡时返回其高度，不平衡时返回False
    # 利用and逻辑的短路性质剪枝，可以提前结束
    def IsBalanced_Solution(self, pRoot):
        # write code here
        if not pRoot:  # 空树的高度设为1（避免高度为0和不平衡的False产生歧义）
            return 1
        l = self.IsBalanced_Solution(pRoot.left)
        if not l:  # 如果左子树不平衡
            return False
        r = self.IsBalanced_Solution(pRoot.right)
        if not r:  # 如果右子树不平衡
            return False
        if abs(l-r) < 2:  # 如果左右子树和本节点均平衡，返回该子树高度
            return 1 + max(l,r)
        else:  # 如果本节点不平衡
            return False
编辑于 2019-08-11 20:51:36 回复(1)
提交观点

问题信息

树 dfs
难度：
48条回答 113920浏览

热门推荐

通过挑战的用户

查看代码

相关试题

判断是不是平衡二叉树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号