199. Binary Tree Right Side View

Description of Problem

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]

Example 2:

Input: root = [1,null,3]
Output: [1,3]

Example 3:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Solution

Tags: Breadth First Search

Explanation

Use two queues to store tree nodes while performing breadth-first search:

queue1 stores tree nodes are ready to be explored.
queue2 stores tree nodes being appended during BFS.

Perform BFS while queue1 is not empty:

Read the last node (the right most) in queue1
For each node in queue1, append its left node and right node in order into queue2.
At the end of an iteration, exchange two queues.

Code (Rust)

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;
impl Solution {
    pub fn right_side_view(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut queue1 = VecDeque::new();
        let mut queue2 = VecDeque::new();
        let mut ans = vec![];

        if let Some(node) = root{
            queue1.push_back(Some(node));
        }   
        
        while !queue1.is_empty(){
            if let Some(&Some(ref node)) = queue1.back(){
                let node = node.borrow();
                ans.push(node.val);
            }

            while let Some(Some(node)) = queue1.pop_front(){
                let node = node.borrow();
                if let Some(left) = node.left.clone(){
                    queue2.push_back(Some(left));
                }
                if let Some(right) = node.right.clone(){
                    queue2.push_back(Some(right));
                }
            }

            let temp = queue1;
            queue1 = queue2;
            queue2 = temp;
        }

        return ans;
    }
}

Complexity

n is the number of nodes in tree
h is the height of tree

Time Complexity

\( T(n) = \Theta(n) \)

Auxiliary Space

\( S(h) = O(2^h) \)

Leetbook