Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 1.The first method checks whether the tree is balanced strictly according to the definition of balanced binary tree: the difference between the heights of the two sub trees are not bigger than 1, and both the left sub tree and right sub tree are also balanced. With the helper function depth(), we could easily write the code;
- class Solution:
- def depth(self, root):
- if not root:
- return 0
- return max(self.depth(root.left), self.depth(root.right)) + 1
- def isBalanced(self, root):
- """
- :type root: TreeNode
- :rtype: bool
- """
- if not root:
- return True
- left = self.depth(root.left)
- right = self.depth(root.right)
- diff = abs(left - right)
- return diff <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)
Add Comment
Please, Sign In to add comment