Binary Tree Right Side View

Problem: https://leetcode.com/problems/binary-tree-right-side-view/description/

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.
Example:
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---
Problem is interesting since you can't really do a DFS otherwise you'll miss some of the far left nodes that need to be in the result list. Notice that all the problem is asking is return the last element for each level of the tree. Level by level: BFS using a queue. Solution is below, thanks, ACC.


public class Solution
{
 public IList RightSideView(TreeNode root)
 {
  if (root == null) return new List();

  QueueItem qi = new QueueItem(root, 0);
  Queue queue = new Queue();
  queue.Enqueue(qi);
  int lastLevel = -1;
  int lastVal = root.val;

  List retVal = new List();
  while (queue.Count > 0)
  {
   qi = (QueueItem)queue.Dequeue();
   if (qi.level > lastLevel)
   {
    retVal.Add(lastVal);
   }
   lastVal = qi.node.val;
   lastLevel = qi.level;

   if (qi.node.left != null)
   {
    QueueItem nqi = new QueueItem(qi.node.left, qi.level + 1);
    queue.Enqueue(nqi);
   }
   if (qi.node.right != null)
   {
    QueueItem nqi = new QueueItem(qi.node.right, qi.level + 1);
    queue.Enqueue(nqi);
   }
  }

  retVal.Add(lastVal);
  return retVal;
 }
}

public class QueueItem
{
 public TreeNode node;
 public int level;

 public QueueItem(TreeNode node, int level)
 {
  this.node = node;
  this.level = level;
 }
}

Comments

  1. Very nice! Usually I don't track levels, since they are not really needed - I prefer to either use 2 queues (current and next) or have a nested loop that iterates the number of times equal to the size of the queue. The implementation based on the first approach is below:

    class Solution {
    public:
    vector rightSideView(TreeNode* root) {
    if (root == nullptr) return {};
    vector view;
    deque current, next;
    current.push_back(root);
    while (!current.empty()) {
    auto node = current.front();
    if (current.size() == 1) view.push_back(node->val);
    current.pop_front();
    if (node->left) next.push_back(node->left);
    if (node->right) next.push_back(node->right);
    if (current.empty() && !next.empty()) swap(current, next);
    }
    return view;
    }
    };

    https://gist.github.com/ttsugriy/0eb14e9108f9615bead3aaf0699dcfcc

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons