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;
}
}
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:
ReplyDeleteclass 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