jinhuang1102

110 Balanced Binary Tree

Nov 18th, 2018
130
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.87 KB | None | 0 0
  1. 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;
  2. class Solution:
  3.     def depth(self, root):
  4.         if not root:
  5.             return 0
  6.        
  7.         return max(self.depth(root.left), self.depth(root.right)) + 1
  8.    
  9.     def isBalanced(self, root):
  10.         """
  11.        :type root: TreeNode
  12.        :rtype: bool
  13.        """
  14.         if not root:
  15.             return True
  16.        
  17.         left = self.depth(root.left)
  18.         right = self.depth(root.right)
  19.        
  20.         diff = abs(left - right)
  21.        
  22.         return diff <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)
Add Comment
Please, Sign In to add comment