forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbinary-tree-right-side-view.py
More file actions
31 lines (29 loc) · 937 Bytes
/
binary-tree-right-side-view.py
File metadata and controls
31 lines (29 loc) · 937 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
"""
perform BFS to the tree:
we traverse every node in the level then go to the next level
every level we traverse from right to left
if it is a level we haven't been through before
we add the node's val to the output
time efficiency is O(N)
because we basically go through all the nodes
N is the total nodes count
space efficiency is O(N)
since we my store the whole level of the tree in the queue
the last level is 0.5N
N is the total nodes count
"""
from collections import deque
class Solution(object):
def rightSideView(self, root):
queue = deque([(root, 0)])
max_level = -1
view = []
while queue:
node, level = queue.popleft()
if node==None: continue
if level>max_level:
max_level = level
view.append(node.val)
queue.append((node.right, level+1))
queue.append((node.left, level+1))
return view