平衡二叉树（二叉树深度+DFS）

题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。平衡二叉树：又称AVL树，具有如下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过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）:
# 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.linuxidc.com/Linux/2016-08/134049.htm根据二叉树的前序数组和中序序遍历数组生成二叉树 http://www.linuxidc.com/Linux/2016-09/135514.htm判断一个二叉树是否是平衡二叉树 http://www.linuxidc.com/Linux/2016-07/132842.htm轻松搞定面试中的二叉树题目 http://www.linuxidc.com/linux/2014-07/104857.htm二叉树的先序、中序、后序遍历 http://www.linuxidc.com/Linux/2016-06/132504.htm本文永久更新链接地址：http://www.linuxidc.com/Linux/2017-01/140042.htm