题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
题目地址
思路
平衡二叉树：它是一棵空树，或者它的两个子树的高度差的绝对值不超过1，并且左右两棵子树都是一棵平衡二叉树。
思路1：
重复遍历多次：
BST的定义为|height(lefttree)−height(righttree)|<=1，原问题拆分为计算树高度和判断高度差
但是，在遍历每个结点时，调用函数TreeDepth得到它的左右子树的深度，如果每个结点的左右子树的深度相差不超过1，则这是一颗平衡的二叉树。这种方法的缺点是，首先判断根结点是不是平衡的，需要使用TreeDepth获得左右子树的深度，然后还需要继续判断子树是不是平衡的，还是需要使用TreeDepth获得子树的左右子树的深度，这导致了大量的重复遍历。
Python
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
# node4.left = node5
class Solution:
def IsBalanced_Solution(self, pRoot):
# write code here
# 思路1 重复遍历多次
if not pRoot:
return True
return abs(self.TreeDepth(pRoot.left)-self.TreeDepth(pRoot.right))<=1
def TreeDepth(self, pRoot):
if not pRoot:
return 0
return max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right))+1
# 思路2 从下往上递归 if __name__ == '__main__':
result = Solution().IsBalanced_Solution(node1)
print(result)