题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
平衡二叉树：又称AVL树，
具有如下性质：
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树(即每一个结点的左右子树)。
# -*- coding:utf-8 -*-# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def IsBalanced_Solution(self, pRoot): # write code here if pRoot is None: return True
def DFS(root):
# 如果说当前结点为None，返回0 if not root: return 0 # 返回左子树和右子树的最大值加1 return max(DFS(root.right), DFS(root.left)) + 1
h1 = DFS(pRoot.right) h2 = DFS(pRoot.left) # 如果说不满足平衡二叉树的性质，返回False if abs(h1 - h2) > 1: return False # 继续判断左子树和右子树是否满足二叉树的性质 return self.IsBalanced_Solution(pRoot.right) and self.IsBalanced_Solution(pRoot.left)
求二叉树中两个节点的最远距离 http://www.xuebuyuan.com/Linux/2016-08/134049.htm
根据二叉树的前序数组和中序序遍历数组生成二叉树 http://www.xuebuyuan.com/Linux/2016-09/135514.htm
判断一个二叉树是否是平衡二叉树 http://www.xuebuyuan.com/Linux/2016-07/132842.htm
轻松搞定面试中的二叉树题目 http://www.xuebuyuan.com/linux/2014-07/104857.htm
二叉树的先序、中序、后序遍历 http://www.xuebuyuan.com/Linux/2016-06/132504.htm
本文永久更新链接地址：http://www.xuebuyuan.com/Linux/2017-01/140042.htm
以上就上有关平衡二叉树(二叉树深度+DFS)的全部内容，学步园全面介绍编程技术、操作系统、数据库、web前端技术等内容。