199. Binary Tree Right Side View
## description
## 199. Binary Tree Right Side View
Given the root of 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.
Example 1:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Explanation:
Example 2:
Input: root = [1,2,3,4,null,null,null,5]
Output: [1,3,4,5]
Explanation:
Example 3:
Input: root = [1,null,3]
Output: [1,3]
Example 4:
Input: root = []
Output: []
- –The number of nodes in the tree is in the range [0, 100].
- –-100 <= Node.val <= 100
Constraints:
## notes
### Intuition
Traverse levels and take the first element in the level ensuring we always add right side to each level first.
### Implementation
Essentially the same as level order traversal but we only want to grab the value from the first node on each level, ensuring to add the right side to the level first always.
Initialize result array and queue that starts with an array of just the root. Iterate while the queue is not empty. Pop the level nodes from the queue and add the value from the first node in the level to the result array (we will ensure that there is always at least one node in the level). Initialize a temporary array for the new level, iterate over the nodes in the current level, if the node has right, add to the new level array, if it has left add to the new level array (always in this order). After that iteration is complete, check if the new level is not empty and append to the queue. Return the result at the end.
### Edge-cases
Return early with empty array if root is None.
Ensure that right side is added to the level first always.
- –Time: O(n), each node is processed once.
- –Space: O(n), the queue can contain all nodes
### Complexity
## solution
1from typing import List, Optional
2from lcutils import TreeNode
3from collections import deque
4
5# Definition for a binary tree node.
6# class TreeNode:
7# def __init__(self, val=0, left=None, right=None):
8# self.val = val
9# self.left = left
10# self.right = right
11class Solution:
12 def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
13 if not root:
14 return []
15 result = []
16 q = deque([[root]])
17 while q:
18 nodes = q.popleft()
19 result.append(nodes[0].val)
20 level = []
21 for node in nodes:
22 if node.right:
23 level.append(node.right)
24 if node.left:
25 level.append(node.left)
26 if level:
27 q.append(level)
28 return result
29
30
31
32if __name__ == "__main__":
33 # Include one-off tests here or debugging logic that can be run by running this file
34 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
35 solution = Solution()
36