GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — algorithms/algorithms/tree/is_balanced.py at master · oldmonad/algorithms Expand file tree/ Copy pathis_balanced.pyMore file actions 36 lines (29 loc) · 828 Bytes / Copy pathis_balanced.pyFile metadata and controls36 lines (29 loc) · 828 Bytes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 def is_balanced(root): return __is_balanced_recursive(root) def __is_balanced_recursive(root): """ O(N) solution """ return -1 != __get_depth(root) def __get_depth(root): """ return 0 if unbalanced else depth + 1 """ if root is None: return 0 left = __get_depth(root.left) right = __get_depth(root.right) if abs(left-right) > 1 or -1 in [left, right]: return -1 return 1 + max(left, right) # def is_balanced(root): # """ # O(N^2) solution # """ # left = max_height(root.left) # right = max_height(root.right) # return abs(left-right) <= 1 and is_balanced(root.left) and is_balanced(root.right) # def max_height(root): # if root is None: # return 0 # return max(max_height(root.left), max_height(root.right)) + 1 |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |