199. Binary Tree Right Side View Leetcode Python
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example: Given the following binary tree,
You should return
This problem can be solved with level order travesal and store the more right element value every time.
This will take O(N) time and O(n) space.
For example: Given the following binary tree,
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return a list of integers
def levelorder(self, root, level, res):
if root:
if len(res)< level + 1:
res.append([])
res[level].append(root.val)
self.levelorder(root.left, level+1, res)
self.levelorder(root.right, level+1, res)
def rightSideView(self, root):
res = []
self.levelorder(root, 0, res)
if res == []:
return res
val = []
for elem in res:
val.append(elem[-1])
return val
1 <---
/ \
2 3 <---
\ \
5 4 <---
You should return
[1, 3, 4]
. This problem can be solved with level order travesal and store the more right element value every time.
This will take O(N) time and O(n) space.