Algorithm
Problem Name: 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]
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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int depth(struct TreeNode *node) {
int d = 0, dl, dr;
if (node) {
dl = depth(node->left);
dr = depth(node->right);
d = dl > dr ? dl : dr;
d += 1;
}
return d;
}
int* rightSideView(struct TreeNode* root, int* returnSize) {
struct TreeNode *node;
struct TreeNode **ns;
int *ds;
int sp = 0;
int *v = NULL;
int d, n = 0, last = 0;
*returnSize = 0;
if (!root) return NULL;
d = depth(root);
ns = malloc(d * sizeof(struct TreeNode *));
v = malloc(d * 2 * sizeof(int));
if (!ns || !v) return NULL;
ds = v + d;
#define PUSH(N, D) do { ns[sp] = N; ds[sp++] = D; } while (0)
#define POP(N, D) do { N = ns[--sp]; D = ds[sp]; } while (0)
d = 1;
PUSH(root, d);
while (sp) {
POP(node, d);
if (d > last) {
v[n ++] = node->val;
last = d;
}
if (node->left) PUSH(node->left, d + 1);
if (node->right) PUSH(node->right, d + 1);
}
*returnSize = n;
free(ns);
return v;
}
Input
root = [1,2,3,null,5,null,4]
Output
[1,3,4]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List rightSideView(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List < Integer> result = new ArrayList<>();
Queue queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
int rightMostValue = -1;
while (size-- > 0) {
TreeNode removed = queue.remove();
rightMostValue = removed.val;
if (removed.left != null) {
queue.add(removed.left);
}
if (removed.right != null) {
queue.add(removed.right);
}
}
result.add(rightMostValue);
}
return result;
}
}
Input
root = [1,2,3,null,5,null,4]
Output
[1,3,4]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const rightSideView = function(root) {
if(root == null) return []
const queue = [root]
const res = []
while(queue.length) {
const len = queue.length
for(let i = 0; i < len; i++) {
const el = queue.shift()
if(i === len - 1) res.push(el.val)
if(el.left) queue.push(el.left)
if(el.right) queue.push(el.right>
}
}
return res
};
Input
root = [1,null,3]
Output
[1,3]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def rightSideView(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
q, res = [root], []
while any(q):
res.append(q[-1].val)
q = [kid for node in q for kid in (node.left, node.right) if kid]
return res
Input
root = [1,null,3]
Output
[1,3]
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0199_BinaryTreeRightSideView
{
public IList < int> RightSideView(TreeNode root)
{
var results = new List<int>();
if (root == null) return results;
var queue = new Queue < TreeNode>();
queue.Enqueue(root);
while (queue.Count > 0)
{
var length = queue.Count;
TreeNode node = null;
for (int i = length; i > 0; i--)
{
node = queue.Dequeue();
if (node.left != null)
queue.Enqueue(node.left);
if (node.right != null)
queue.Enqueue(node.right);
}
results.Add(node.val);
}
return results;
}
}
}
Input
root = []
Output
[]