Dado un árbol binario, imprima la vista inferior derecha del mismo. La vista inferior derecha de un árbol binario es un conjunto de Nodes visibles cuando se visita el árbol desde el lado inferior derecho, devuelve los valores de los Nodes ordenados de derecha a izquierda.
En la vista inferior derecha, al ver el árbol en un ángulo de 45 grados desde el lado inferior derecho, solo unos pocos Nodes serían visibles y el resto estaría oculto detrás de ellos.
Ejemplos:
Input :
1
/ \
2 3
\ \
5 4
Output : [4, 5]
Visible nodes from the bottom right direction are 4 and 5
Input :
1
/ \
2 3
/ /
4 5
\
6
Output: [3, 6, 4]
Acercarse :
- El problema se puede resolver mediante un recorrido recursivo simple.
- Realice un seguimiento del nivel de un Node pasando un parámetro a todas las llamadas recursivas. Considere el nivel de un árbol en un ángulo del 45% (como se explica en un ejemplo), por lo que cada vez que nos movemos hacia la izquierda, su nivel aumentaría en uno.
- La idea es realizar un seguimiento del nivel máximo y atravesar el árbol de manera que el subárbol derecho se visite antes que el subárbol izquierdo.
- Un Node cuyo nivel es mayor que el nivel máximo hasta el momento, Imprima el Node porque este es el último Node en su nivel (Atraviese el subárbol derecho antes del subárbol izquierdo).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print bottom
// right view of binary tree
#include<bits/stdc++.h>
using namespace std;
// A binary tree node
struct Node
{
int data;
Node *left, *right;
Node(int item)
{
data = item;
left = right = NULL;
}
};
// class to access maximum level
// by reference
struct _Max_level
{
int _max_level;
};
Node *root;
_Max_level *_max = new _Max_level();
// Recursive function to print bottom
// right view of a binary tree
void bottomRightViewUtil(Node* node, int level,
_Max_level *_max_level)
{
// Base Case
if (node == NULL)
return;
// Recur for right subtree first
bottomRightViewUtil(node->right,
level, _max_level);
// If this is the last Node of its level
if (_max_level->_max_level < level)
{
cout << node->data << " ";
_max_level->_max_level = level;
}
// Recur for left subtree
// with increased level
bottomRightViewUtil(node->left,
level + 1, _max_level);
}
// A wrapper over bottomRightViewUtil()
void bottomRightView(Node *node)
{
bottomRightViewUtil(node, 1, _max);
}
void bottomRightView()
{
bottomRightView(root);
}
// Driver Code
int main()
{
root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->right->left = new Node(5);
root->right->left->right = new Node(6);
bottomRightView();
}
// This code is contributed by Arnab Kundu
Java
// Java program to print bottom
// right view of binary tree
// A binary tree node
class Node {
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
// class to access maximum level by reference
class Max_level {
int max_level;
}
class BinaryTree {
Node root;
Max_level max = new Max_level();
// Recursive function to print bottom
// right view of a binary tree.
void bottomRightViewUtil(Node node, int level,
Max_level max_level)
{
// Base Case
if (node == null)
return;
// Recur for right subtree first
bottomRightViewUtil(node.right,
level, max_level);
// If this is the last Node of its level
if (max_level.max_level < level) {
System.out.print(node.data + " ");
max_level.max_level = level;
}
// Recur for left subtree with increased level
bottomRightViewUtil(node.left,
level + 1, max_level);
}
void bottomRightView()
{
bottomRightView(root);
}
// A wrapper over bottomRightViewUtil()
void bottomRightView(Node node)
{
bottomRightViewUtil(node, 1, max);
}
// Driver program to test the above functions
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.right.left = new Node(5);
tree.root.right.left.right = new Node(6);
tree.bottomRightView();
}
}
Python3
# Python3 program to print bottom # right view of binary tree # A binary tree node class Node: # Construct to create a newNode def __init__(self, item): self.data = item self.left = None self.right = None maxlevel = [0] # Recursive function to print bottom # right view of a binary tree. def bottomRightViewUtil(node, level, maxlevel): # Base Case if (node == None): return # Recur for right subtree first bottomRightViewUtil(node.right, level, maxlevel) # If this is the last Node of its level if (maxlevel[0] < level): print(node.data, end = " ") maxlevel[0] = level # Recur for left subtree with increased level bottomRightViewUtil(node.left, level + 1, maxlevel) # A wrapper over bottomRightViewUtil() def bottomRightView(node): bottomRightViewUtil(node, 1, maxlevel) # Driver Code root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.right.left = Node(5) root.right.left.right = Node(6) bottomRightView(root) # This code is contributed by SHUBHAMSINGH10
C#
// C# program to print bottom
// right view of binary tree
using System;
// A binary tree node
class Node
{
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
// class to access maximum level by reference
class Max_level
{
public int max_level;
}
class GFG
{
Node root;
Max_level max = new Max_level();
// Recursive function to print bottom
// right view of a binary tree.
void bottomRightViewUtil(Node node, int level,
Max_level max_level)
{
// Base Case
if (node == null)
return;
// Recur for right subtree first
bottomRightViewUtil(node.right,
level, max_level);
// If this is the last Node of its level
if (max_level.max_level < level)
{
Console.Write(node.data + " ");
max_level.max_level = level;
}
// Recur for left subtree with increased level
bottomRightViewUtil(node.left,
level + 1, max_level);
}
void bottomRightView()
{
bottomRightView(root);
}
// A wrapper over bottomRightViewUtil()
void bottomRightView(Node node)
{
bottomRightViewUtil(node, 1, max);
}
// Driver Code
public static void Main(String []args)
{
GFG tree = new GFG();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.right.left = new Node(5);
tree.root.right.left.right = new Node(6);
tree.bottomRightView();
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to print bottom
// right view of binary tree
// A binary tree node
class Node
{
constructor(item)
{
this.data = item;
this.left = null;
this.right = null;
}
}
// class to access maximum level by reference
class Max_level
{
constructor()
{
this.max_level = 0;
}
}
var max = new Max_level();
// Recursive function to print bottom
// right view of a binary tree.
function bottomRightViewUtil(node, level,max_level)
{
// Base Case
if (node == null)
return;
// Recur for right subtree first
bottomRightViewUtil(node.right,
level, max_level);
// If this is the last Node of its level
if (max_level.max_level < level)
{
document.write(node.data + " ");
max_level.max_level = level;
}
// Recur for left subtree with increased level
bottomRightViewUtil(node.left,
level + 1, max_level);
}
// A wrapper over bottomRightViewUtil()
function bottomRightView(node)
{
bottomRightViewUtil(node, 1, max);
}
// Driver Code
var root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.right.left = new Node(5);
root.right.left.right = new Node(6);
bottomRightView(root);
// This code is contributed by rrrtnx.
</script>
Producción:
3 6 4
Complejidad temporal: O(N), donde N es el número de Nodes del árbol binario.
Publicación traducida automáticamente
Artículo escrito por mayankbansal2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA