FilesExpand file tree

 master

/

balanced_binary_tree.py

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

35 lines (25 loc) · 970 Bytes

 master

/

balanced_binary_tree.py

Top

File metadata and controls

• Code
• Blame

35 lines (25 loc) · 970 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

#!/usr/bin/env python

'''

Leetcode: Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

'''

from __future__ import division

import random

from BinaryTree import Node, SampleTreeRoot

# return, True/False (whether balanced), height of the tree

import math

def balanced_binary_tree(root):

if not root:

return True, 0

if not root.left and not root.right:

return True, 1

balance_left, left = balanced_binary_tree(root.left)

balance_right, right = balanced_binary_tree(root.right)

is_balanced = (math.fabs(left-right) <=1 and balance_left and balance_right)

tree_height = max(left, right) + 1

return is_balanced, tree_height

if __name__ == '__main__':

root = SampleTreeRoot

print root

print balanced_binary_tree(root)