FilesExpand file tree

 master

/

printTree.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

20 lines (17 loc) · 700 Bytes

 master

/

printTree.py

Copy path

Top

File metadata and controls

• Code
• Blame

20 lines (17 loc) · 700 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

# recursive solution: takes O(n) time

# first get the height of the tree, then recusivly update the value

def printTree(self, root):

def get_height(root):

if not root: return 0

return 1 + max(get_height(root.left), get_height(root.right))

def update(res, node, row, left, right):

if not node: return

mid = (left + right) // 2

res[row][mid] = str(node.val)

update(res, node.left, row + 1, left, mid - 1)

update(res, node.right, row + 1, mid + 1, right)

height = get_height(root)

width = 2 ** height - 1

res = [['' for _ in range(width)] for _ in range(height)]

update(res, root, 0, 0, width - 1)

return res