题目描述：输入一棵二叉树，判断该二叉树是否是平衡二叉树。
Solutions
这个题目是二叉树的深度的拓展题目，这要求弄清楚平衡二叉树的概念，只要某二叉树中任意结点的左右子树深度相差不超过 1。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def TreeDepth(self, pRoot):
# write code here
if pRoot is None:
return 0
left_depth = self.TreeDepth(pRoot.left)
right_depth = self.TreeDepth(pRoot.right)
return left_depth + 1 if left_depth > right_depth else right_depth + 1
def IsBalanced_Solution(self, pRoot):
# write code here
if pRoot is None:
return True
left_depth = self.TreeDepth(pRoot.left)
right_depth = self.TreeDepth(pRoot.right)
diff = left_depth - right_depth
if diff > 1 or diff < -1:
return False
return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
# 运行时间：28ms
# 占用内存：6476k
但是这个效果是不尽人意的，因为对树进行了多次遍历，效率较低。那么我们可以从遍历方式上做一个改进，我们利用后序遍历方式遍历整棵二叉树，判断是否是平衡二叉树，在遍历时我们记录每个节点的深度。根据书本上可以写成如下的代码：
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def IsBalanced(self, pRoot, depth):
if pRoot is None:
depth = 0
return True, depth
is_left_balanced, left_depth = self.IsBalanced(pRoot.left, depth)
is_right_balanced, right_depth = self.IsBalanced(pRoot.right, depth)
if is_left_balanced and is_right_balanced:
diff = left_depth - right_depth
if diff <= 1 and diff >= -1:
depth = max(left_depth, right_depth) + 1
return True, depth
return False, depth
def IsBalanced_Solution(self, pRoot):
# write code here
depth = 0
flag, _ = self.IsBalanced(pRoot, depth)
return flag
# 运行时间：23ms
# 占用内存：5752k
抛开二叉树深度那个题目的干扰，我们直接自下向上的递归判断是否为平衡二叉树：
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def balance_height(self, pRoot):
if pRoot is None:
return 0
left_height = self.balance_height(pRoot.left)
right_height = self.balance_height(pRoot.right)
if left_height < 0 or right_height < 0 or abs(left_height - right_height) > 1:
return -1
return max(left_height, right_height) + 1
def IsBalanced_Solution(self, pRoot):
# write code here
return self.balance_height(pRoot) >= 0
# 运行时间：25ms
# 占用内存：5864k