题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
思路
思路1：非剪枝
递归查看每棵子树是否满足平衡二叉树，o(nlogn)复杂度。
思路2：剪枝
看子树是否是平衡二叉树，如果不是返回-1，如果是返回长度。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def getDeep(x):
if x is None:
return 0
return 1 + max(getDeep(x.left), getDeep(x.right))
class Solution:
def IsBalanced_Solution(self, pRoot):
# write code here
if not pRoot:
return 1
return abs(getDeep(pRoot.left)-getDeep(pRoot.right)) <= 1 \
and IsBalanced_Solution(pRoot.left) \
and IsBalanced_Solution(pRoot.right) def getDeep(x):
if x is None:
return 0
left = getDeep(x.left)
if left == -1:
return -1
right = getDeep(x.right)
if right == -1:
return -1
return -1 if abs(left-right) > 1 else 1 + max(left, right)
class Solution:
def IsBalanced_Solution(self, pRoot):
# write code here
return getDeep(pRoot) != -1