Dado un árbol binario y una clave en el árbol binario, encuentre el Node derecho a la clave dada. Si no hay ningún Node en el lado derecho, devuelva NULL. La complejidad de tiempo esperada es O(n) donde n es el número de Nodes en el árbol binario dado.
Por ejemplo, considere el siguiente árbol binario. La salida para 2 es 6, la salida para 4 es 5. La salida para 10, 6 y 5 es NULL.
10
/ \
2 6
/ \ \
8 4 5
Input : 2
Output : 6
Input : 4
Output : 5
En nuestra publicación anterior , hemos discutido sobre una solución que usa Level Order Traversal . En esta publicación, discutiremos sobre una solución basada en el recorrido Preorder que ocupa un espacio auxiliar constante.
La idea es recorrer el árbol dado utilizando el recorrido de preorden y buscar la clave dada. Una vez que encontramos la clave dada, marcaremos el número de nivel para esta clave. Ahora el siguiente Node que encontraremos en el mismo nivel es el Node requerido que está a la derecha de la clave dada.
A continuación se muestra la implementación de la idea anterior:
C++
/* C++ program to find next right of a given key
using preorder traversal */
#include <bits/stdc++.h>
using namespace std;
// A Binary Tree Node
struct Node {
struct Node *left, *right;
int key;
};
// Utility function to create a new tree node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
}
// Function to find next node for given node
// in same level in a binary tree by using
// pre-order traversal
Node* nextRightNode(Node* root, int k, int level,
int& value_level)
{
// return null if tree is empty
if (root == NULL)
return NULL;
// if desired node is found, set value_level
// to current level
if (root->key == k) {
value_level = level;
return NULL;
}
// if value_level is already set, then current
// node is the next right node
else if (value_level) {
if (level == value_level)
return root;
}
// recurse for left subtree by increasing level by 1
Node* leftNode = nextRightNode(root->left, k,
level + 1, value_level);
// if node is found in left subtree, return it
if (leftNode)
return leftNode;
// recurse for right subtree by increasing level by 1
return nextRightNode(root->right, k, level + 1,
value_level);
}
// Function to find next node of given node in the
// same level in given binary tree
Node* nextRightNodeUtil(Node* root, int k)
{
int value_level = 0;
return nextRightNode(root, k, 1, value_level);
}
// A utility function to test above functions
void test(Node* root, int k)
{
Node* nr = nextRightNodeUtil(root, k);
if (nr != NULL)
cout << "Next Right of " << k << " is "
<< nr->key << endl;
else
cout << "No next right node found for "
<< k << endl;
}
// Driver program to test above functions
int main()
{
// Let us create binary tree given in the
// above example
Node* root = newNode(10);
root->left = newNode(2);
root->right = newNode(6);
root->right->right = newNode(5);
root->left->left = newNode(8);
root->left->right = newNode(4);
test(root, 10);
test(root, 2);
test(root, 6);
test(root, 5);
test(root, 8);
test(root, 4);
return 0;
}
Java
/* Java program to find next right of a given key
using preorder traversal */
import java.util.*;
class GfG {
// A Binary Tree Node
static class Node {
Node left, right;
int key;
}
// Utility function to create a new tree node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = null;
temp.right = null;
return temp;
}
// Function to find next node for given node
// in same level in a binary tree by using
// pre-order traversal
static Node nextRightNode(Node root, int k, int level, int[] value)
{
// return null if tree is empty
if (root == null)
return null;
// if desired node is found, set value[0]
// to current level
if (root.key == k) {
value[0] = level;
return null;
}
// if value[0] is already set, then current
// node is the next right node
else if (value[0] != 0) {
if (level == value[0])
return root;
}
// recurse for left subtree by increasing level by 1
Node leftNode = nextRightNode(root.left, k, level + 1, value);
// if node is found in left subtree, return it
if (leftNode != null)
return leftNode;
// recurse for right subtree by increasing level by 1
return nextRightNode(root.right, k, level + 1, value);
}
// Function to find next node of given node in the
// same level in given binary tree
static Node nextRightNodeUtil(Node root, int k)
{
int[] v = new int[1];
v[0] = 0;
return nextRightNode(root, k, 1, v);
}
// A utility function to test above functions
static void test(Node root, int k)
{
Node nr = nextRightNodeUtil(root, k);
if (nr != null)
System.out.println("Next Right of " + k + " is "+ nr.key);
else
System.out.println("No next right node found for " + k);
}
// Driver program to test above functions
public static void main(String[] args)
{
// Let us create binary tree given in the
// above example
Node root = newNode(10);
root.left = newNode(2);
root.right = newNode(6);
root.right.right = newNode(5);
root.left.left = newNode(8);
root.left.right = newNode(4);
test(root, 10);
test(root, 2);
test(root, 6);
test(root, 5);
test(root, 8);
test(root, 4);
}
}
// This code has been contributed by Mukul Sharma
Python3
# Python3 program to find next right of a
# given key using preorder traversal
# class to create a new tree node
class newNode:
def __init__(self, key):
self.key = key
self.left = self.right = None
# Function to find next node for given node
# in same level in a binary tree by using
# pre-order traversal
def nextRightNode(root, k, level, value_level):
# return None if tree is empty
if (root == None):
return None
# if desired node is found, set
# value_level to current level
if (root.key == k):
value_level[0] = level
return None
# if value_level is already set, then
# current node is the next right node
elif (value_level[0]):
if (level == value_level[0]):
return root
# recurse for left subtree by increasing
# level by 1
leftNode = nextRightNode(root.left, k,
level + 1, value_level)
# if node is found in left subtree,
# return it
if (leftNode):
return leftNode
# recurse for right subtree by
# increasing level by 1
return nextRightNode(root.right, k,
level + 1, value_level)
# Function to find next node of given node
# in the same level in given binary tree
def nextRightNodeUtil(root, k):
value_level = [0]
return nextRightNode(root, k, 1, value_level)
# A utility function to test above functions
def test(root, k):
nr = nextRightNodeUtil(root, k)
if (nr != None):
print("Next Right of", k, "is", nr.key)
else:
print("No next right node found for", k)
# Driver Code
if __name__ == '__main__':
# Let us create binary tree given in the
# above example
root = newNode(10)
root.left = newNode(2)
root.right = newNode(6)
root.right.right = newNode(5)
root.left.left = newNode(8)
root.left.right = newNode(4)
test(root, 10)
test(root, 2)
test(root, 6)
test(root, 5)
test(root, 8)
test(root, 4)
# This code is contributed by PranchalK
C#
/* C# program to find next right of a given key
using preorder traversal */
using System;
class GfG
{
public class V
{
public int value_level = 0;
}
// A Binary Tree Node
public class Node
{
public Node left, right;
public int key;
}
// Utility function to create a new tree node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = null;
temp.right = null;
return temp;
}
// Function to find next node for given node
// in same level in a binary tree by using
// pre-order traversal
static Node nextRightNode(Node root, int k,
int level, V value)
{
// return null if tree is empty
if (root == null)
return null;
// if desired node is found, set
// value_level to current level
if (root.key == k)
{
value.value_level = level;
return null;
}
// if value_level is already set, then current
// node is the next right node
else if (value.value_level != 0)
{
if (level == value.value_level)
return root;
}
// recurse for left subtree by increasing level by 1
Node leftNode = nextRightNode(root.left,
k, level + 1, value);
// if node is found in left subtree, return it
if (leftNode != null)
return leftNode;
// recurse for right subtree by
// increasing level by 1
return nextRightNode(root.right, k,
level + 1, value);
}
// Function to find next node of given node in the
// same level in given binary tree
static Node nextRightNodeUtil(Node root, int k)
{
V v = new V();
return nextRightNode(root, k, 1, v);
}
// A utility function to test above functions
static void test(Node root, int k)
{
Node nr = nextRightNodeUtil(root, k);
if (nr != null)
Console.WriteLine("Next Right of " +
k + " is "+ nr.key);
else
Console.WriteLine("No next right node" +
" found for " + k);
}
// Driver main
public static void Main(String[] args)
{
// Let us create binary tree given in the
// above example
Node root = newNode(10);
root.left = newNode(2);
root.right = newNode(6);
root.right.right = newNode(5);
root.left.left = newNode(8);
root.left.right = newNode(4);
test(root, 10);
test(root, 2);
test(root, 6);
test(root, 5);
test(root, 8);
test(root, 4);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
/* Javascript program to find next right of a given key
using preorder traversal */
// A Binary Tree Node
class Node
{
constructor(key) {
this.left = null;
this.right = null;
this.key = key;
}
}
// Utility function to create a new tree node
function newNode(key)
{
let temp = new Node(key);
return temp;
}
// Function to find next node for given node
// in same level in a binary tree by using
// pre-order traversal
function nextRightNode(root, k, level, value)
{
// return null if tree is empty
if (root == null)
return null;
// if desired node is found, set value[0]
// to current level
if (root.key == k) {
value[0] = level;
return null;
}
// if value[0] is already set, then current
// node is the next right node
else if (value[0] != 0) {
if (level == value[0])
return root;
}
// recurse for left subtree by increasing level by 1
let leftNode = nextRightNode(root.left, k, level + 1, value);
// if node is found in left subtree, return it
if (leftNode != null)
return leftNode;
// recurse for right subtree by increasing level by 1
return nextRightNode(root.right, k, level + 1, value);
}
// Function to find next node of given node in the
// same level in given binary tree
function nextRightNodeUtil(root, k)
{
let v = new Array(1);
v[0] = 0;
return nextRightNode(root, k, 1, v);
}
// A utility function to test above functions
function test(root, k)
{
let nr = nextRightNodeUtil(root, k);
if (nr != null)
document.write("Next Right of " + k + " is "+ nr.key +
"</br>");
else
document.write("No next right node found for " + k +
"</br>");
}
// Let us create binary tree given in the
// above example
let root = newNode(10);
root.left = newNode(2);
root.right = newNode(6);
root.right.right = newNode(5);
root.left.left = newNode(8);
root.left.right = newNode(4);
test(root, 10);
test(root, 2);
test(root, 6);
test(root, 5);
test(root, 8);
test(root, 4);
</script>
Salida :
No next right node found for 10 Next Right of 2 is 6 No next right node found for 6 No next right node found for 5 Next Right of 8 is 4 Next Right of 4 is 5
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por harsh.agarwal0 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA