Title: Binary Tree Right Side View Source: leetcode.com
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 4 5 |
1 <--- / \ 2 3 <--- \ \ 5 4 <--- |
You should return [1, 3, 4].
Python solution
|
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 32 33 34 35 36 37 38 39 40 41 42 |
''' https://leetcode.com/problems/binary-tree-right-side-view/ ''' # 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 __init__(self): self.rsv = [] self.d = {} def helper(self, root, lvl): if root.right: if not self.d[lvl]: self.rsv.append(root.right.val) self.d[lvl] = True if (lvl+1) not in self.d: self.d[lvl + 1] = False self.helper(root.right, lvl + 1) if root.left: if not self.d[lvl]: self.rsv.append(root.left.val) self.d[lvl] = True if (lvl+1) not in self.d: self.d[lvl + 1] = False self.helper(root.left, lvl + 1) def rightSideView(self, root): """ :type root: TreeNode :rtype: List[int] """ if not root: return self.rsv self.rsv.append(root.val) self.d[1] = False self.helper(root, 1) return self.rsv |