题目描述
输入一棵二叉树,判断该二叉树是否是平衡二叉树。
思路
思路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