本文共 1441 字，大约阅读时间需要 4 分钟。

题目：输入一棵二叉树，判断该二叉树是否是平衡二叉树。在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树。平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

方法一：

直接写一个函数计算二叉树的深度，然后按照题目中平衡二叉树的定义去判断。

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

方法二：

引入深度优先搜索（DFS）的思想，从如果一个某一个子树不是平衡二叉树，那么就不需要后续的判断了。因此对求解树的深度的函数进行改进。

class Solution:    def IsBalanced_Solution(self, pRoot):        # write code here        def tree_deepth(pRoot):            if not pRoot:                return 0            #对左子树进行搜索，并在出现非平衡子树时返回-1并结束            left = tree_deepth(pRoot.left)            if left == -1:                return -1            #对右子树进行搜索，并在出现非平衡子树时返回-1并结束            right = tree_deepth(pRoot.right)            if right == -1:                return -1            #判断左右子树的深度之差是否满足要求            if abs(left - right) > 1:                return -1            #正常情况下返回二叉树深度            return max(left,right)+1        return tree_deepth(pRoot) != -1

转载地址：https://blog.csdn.net/sinat_42437278/article/details/117714886 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！