思路:后序遍历的方式遍历二叉树的每个节点,只要在遍历每个节点的时候记录它的深度,就可以一边遍历一边判断每个节点是不是平衡的
思路二:类似求二叉树深度的递归方式,递归返回结果两个,一个返回子树是否是平衡二叉树,一个返回深度
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
self.res = True
def helper(root):
if not root:
return 0
left = helper(root.left) + 1
right = helper(root.right) + 1
#print(right, left)
if abs(right - left) > 1:
self.res = False
return max(left, right)
helper(root)
return self.res