Given the root of a binary tree root
, return an array with the the "right side view" of the tree.
Example:
We can't do a greedy solution that just goes down the rightmost branch, because that branch might end, exposing other branches. We need to traverse the tree layer-by-layer, taking the rightmost node at each layer.
We should use a BFS since a BFS goes layer-by-layer naturally. Here's the code for a BFS from the lesson:
Now, how do we find the rightmost node in each layer of the BFS?
Remember that the line for _ in range(len(queue))
visits nodes layer by layer.
For example, here's what the queue looks like after visiting the 1st layer:
And here's what it looks like after visiting the 2nd layer:
The rightmost node is always the last element in the queue, queue[-1]
. So to solve the problem, we'll keep an array of all the rightmost nodes we've seen so far in an array, called soln
. We just stick a few lines of code into the BFS:
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()