FilesExpand file tree

 master

/

max_height.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

54 lines (46 loc) · 1.14 KB

 master

/

max_height.py

Copy path

Top

File metadata and controls

• Code
• Blame

54 lines (46 loc) · 1.14 KB

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

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

"""

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the

longest path from the root node down to the farthest leaf node.

"""

class Node():

def __init__(self, val = 0):

self.val = val

self.left = None

self.right = None

# def max_height(root):

# if not root:

# return 0

# return max(maxDepth(root.left), maxDepth(root.right)) + 1

# iterative

def max_height(root):

if not root:

return 0

height = 0

queue = [root]

while queue:

height += 1

level = []

while queue:

node = queue.pop(0)

if node.left:

level.append(node.left)

if node.right:

level.append(node.right)

queue = level

return height

def print_tree(root):

if root:

print(root.val)

print_tree(root.left)

print_tree(root.right)

tree = Node(10)

tree.left = Node(12)

tree.right = Node(15)

tree.left.left = Node(25)

tree.left.left.right = Node(100)

tree.left.right = Node(30)

tree.right.left = Node(36)

height = max_height(tree)

print_tree(tree)

print("height:", height)