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.