题解 | #判断是不是平衡二叉树#
判断是不是平衡二叉树
http://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222
解题思路:
- 感觉这道题要对递归的运行原理很熟悉才能看得懂
- 两个递归,从下往上的判断是否符合高度差不超过1
- left, right会一直进递归,直到叶子结点return 0,解决了我初始值的困惑
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
#
# @param pRoot TreeNode类
# @return bool布尔型
#
class Solution:
def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
# write code here
if not pRoot:
return True
left = self.depth(pRoot.left)
right = self.depth(pRoot.right)
if abs(left-right) > 1:
return False
return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
def depth(self, root):
if not root:
return 0
left = self.depth(root.left)
right = self.depth(root.right)
return max(left, right) + 1