199. Binary Tree Right Side View
- Total Accepted: 56659
- Total Submissions: 151351
- Difficulty: Medium
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,
1 <--- / \ 2 3 <--- \ \ 5 4 <---
You should return [1, 3, 4].
Code (recursion)
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def rightSideView(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
self.recursion(root, 1, res)
return res
def recursion(self, node, level, res):
if node is None:
return res
if len(res) < level:
res.append(node.val)
self.recursion(node.right, level+1, res)
self.recursion(node.left, level+1, res)
Code
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import deque
class Solution(object):
def rightSideView(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root is None:
return []
res = []
q = deque([(root, 0)])
last_v = 0
last_l = 0
while q:
n, l = q.popleft()
if l > last_l:
res.append(last_v)
last_l = l
last_v = n.val
if n.left is not None:
q.append((n.left, l+1))
if n.right is not None:
q.append((n.right, l+1))
res.append(last_v)
return res
Idea
Core idea is to have level recorded during traversal.