Dado un árbol binario con punteros principales, encuentre el hermano correcto de un Node dado (se dará el puntero al Node), si no existe, devuelva nulo. ¿Hacerlo en O(1) espacio y O(n) tiempo?
Ejemplos:
1
/ \
2 3
/ \ \
4 6 5
/ \ \
7 9 8
/ \
10 12
Input : Given above tree with parent pointer and node 10
Output : 12
Enfoque: la idea es encontrar el primer hijo derecho del antepasado más cercano que no es ni el Node actual ni el padre del Node actual, realizar un seguimiento del nivel en esos mientras sube. luego, iterar a través de ese Node, primero el hijo izquierdo, si el izquierdo no está allí, entonces, el hijo derecho y si el nivel se convierte en 0, entonces, este es el siguiente hermano derecho del Node dado.
En el caso anterior, si el Node dado es 7, terminaremos con 6 para encontrar el hijo correcto que no tiene ningún hijo.
En este caso, necesitamos llamar recursivamente al hermano correcto con el nivel actual, para que lleguemos a 8.
Implementación:
C++
// C program to print right sibling of a node
#include <bits/stdc++.h>
// A Binary Tree Node
struct Node {
int data;
Node *left, *right, *parent;
};
// A utility function to create a new Binary
// Tree Node
Node* newNode(int item, Node* parent)
{
Node* temp = new Node;
temp->data = item;
temp->left = temp->right = NULL;
temp->parent = parent;
return temp;
}
// Method to find right sibling
Node* findRightSibling(Node* node, int level)
{
if (node == NULL || node->parent == NULL)
return NULL;
// GET Parent pointer whose right child is not
// a parent or itself of this node. There might
// be case when parent has no right child, but,
// current node is left child of the parent
// (second condition is for that).
while (node->parent->right == node
|| (node->parent->right == NULL
&& node->parent->left == node)) {
if (node->parent == NULL
|| node->parent->parent == NULL)
return NULL;
node = node->parent;
level--;
}
// Move to the required child, where right sibling
// can be present
node = node->parent->right;
if (node == NULL)
return NULL;
// find right sibling in the given subtree(from current
// node), when level will be 0
while (level < 0) {
// Iterate through subtree
if (node->left != NULL)
node = node->left;
else if (node->right != NULL)
node = node->right;
else
// if no child are there, we cannot have right
// sibling in this path
break;
level++;
}
if (level == 0)
return node;
// This is the case when we reach 9 node in the tree,
// where we need to again recursively find the right
// sibling
return findRightSibling(node, level);
}
// Driver Program to test above functions
int main()
{
Node* root = newNode(1, NULL);
root->left = newNode(2, root);
root->right = newNode(3, root);
root->left->left = newNode(4, root->left);
root->left->right = newNode(6, root->left);
root->left->left->left = newNode(7, root->left->left);
root->left->left->left->left = newNode(10, root->left->left->left);
root->left->right->right = newNode(9, root->left->right);
root->right->right = newNode(5, root->right);
root->right->right->right = newNode(8, root->right->right);
root->right->right->right->right = newNode(12, root->right->right->right);
// passing 10
Node* res = findRightSibling(root->left->left->left->left, 0);
if (res == NULL)
printf("No right sibling");
else
printf("%d", res->data);
return 0;
}
Java
// Java program to print right sibling of a node
public class Right_Sibling {
// A Binary Tree Node
static class Node {
int data;
Node left, right, parent;
// Constructor
public Node(int data, Node parent)
{
this.data = data;
left = null;
right = null;
this.parent = parent;
}
};
// Method to find right sibling
static Node findRightSibling(Node node, int level)
{
if (node == null || node.parent == null)
return null;
// GET Parent pointer whose right child is not
// a parent or itself of this node. There might
// be case when parent has no right child, but,
// current node is left child of the parent
// (second condition is for that).
while (node.parent.right == node
|| (node.parent.right == null
&& node.parent.left == node)) {
if (node.parent == null)
return null;
node = node.parent;
level--;
}
// Move to the required child, where right sibling
// can be present
node = node.parent.right;
// find right sibling in the given subtree(from current
// node), when level will be 0
while (level < 0) {
// Iterate through subtree
if (node.left != null)
node = node.left;
else if (node.right != null)
node = node.right;
else
// if no child are there, we cannot have right
// sibling in this path
break;
level++;
}
if (level == 0)
return node;
// This is the case when we reach 9 node in the tree,
// where we need to again recursively find the right
// sibling
return findRightSibling(node, level);
}
// Driver Program to test above functions
public static void main(String args[])
{
Node root = new Node(1, null);
root.left = new Node(2, root);
root.right = new Node(3, root);
root.left.left = new Node(4, root.left);
root.left.right = new Node(6, root.left);
root.left.left.left = new Node(7, root.left.left);
root.left.left.left.left = new Node(10, root.left.left.left);
root.left.right.right = new Node(9, root.left.right);
root.right.right = new Node(5, root.right);
root.right.right.right = new Node(8, root.right.right);
root.right.right.right.right = new Node(12, root.right.right.right);
// passing 10
System.out.println(findRightSibling(root.left.left.left.left, 0).data);
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python3 program to print right sibling
# of a node
# A class to create a new Binary
# Tree Node
class newNode:
def __init__(self, item, parent):
self.data = item
self.left = self.right = None
self.parent = parent
# Method to find right sibling
def findRightSibling(node, level):
if (node == None or node.parent == None):
return None
# GET Parent pointer whose right child is not
# a parent or itself of this node. There might
# be case when parent has no right child, but,
# current node is left child of the parent
# (second condition is for that).
while (node.parent.right == node or
(node.parent.right == None and
node.parent.left == node)):
if (node.parent == None):
return None
node = node.parent
level -= 1
# Move to the required child, where
# right sibling can be present
node = node.parent.right
# find right sibling in the given subtree
# (from current node), when level will be 0
while (level < 0):
# Iterate through subtree
if (node.left != None):
node = node.left
else if (node.right != None):
node = node.right
else:
# if no child are there, we cannot
# have right sibling in this path
break
level += 1
if (level == 0):
return node
# This is the case when we reach 9 node
# in the tree, where we need to again
# recursively find the right sibling
return findRightSibling(node, level)
# Driver Code
if __name__ == '__main__':
root = newNode(1, None)
root.left = newNode(2, root)
root.right = newNode(3, root)
root.left.left = newNode(4, root.left)
root.left.right = newNode(6, root.left)
root.left.left.left = newNode(7, root.left.left)
root.left.left.left.left = newNode(10, root.left.left.left)
root.left.right.right = newNode(9, root.left.right)
root.right.right = newNode(5, root.right)
root.right.right.right = newNode(8, root.right.right)
root.right.right.right.right = newNode(12, root.right.right.right)
# passing 10
res = findRightSibling(root.left.left.left.left, 0)
if (res == None):
print("No right sibling")
else:
print(res.data)
# This code is contributed by PranchalK
C#
using System;
// C# program to print right sibling of a node
public class Right_Sibling {
// A Binary Tree Node
public class Node {
public int data;
public Node left, right, parent;
// Constructor
public Node(int data, Node parent)
{
this.data = data;
left = null;
right = null;
this.parent = parent;
}
}
// Method to find right sibling
public static Node findRightSibling(Node node, int level)
{
if (node == null || node.parent == null) {
return null;
}
// GET Parent pointer whose right child is not
// a parent or itself of this node. There might
// be case when parent has no right child, but,
// current node is left child of the parent
// (second condition is for that).
while (node.parent.right == node
|| (node.parent.right == null
&& node.parent.left == node)) {
if (node.parent == null
|| node.parent.parent == null) {
return null;
}
node = node.parent;
level--;
}
// Move to the required child, where right sibling
// can be present
node = node.parent.right;
// find right sibling in the given subtree(from current
// node), when level will be 0
while (level < 0) {
// Iterate through subtree
if (node.left != null) {
node = node.left;
}
else if (node.right != null) {
node = node.right;
}
else {
// if no child are there, we cannot have right
// sibling in this path
break;
}
level++;
}
if (level == 0) {
return node;
}
// This is the case when we reach 9 node in the tree,
// where we need to again recursively find the right
// sibling
return findRightSibling(node, level);
}
// Driver Program to test above functions
public static void Main(string[] args)
{
Node root = new Node(1, null);
root.left = new Node(2, root);
root.right = new Node(3, root);
root.left.left = new Node(4, root.left);
root.left.right = new Node(6, root.left);
root.left.left.left = new Node(7, root.left.left);
root.left.left.left.left = new Node(10, root.left.left.left);
root.left.right.right = new Node(9, root.left.right);
root.right.right = new Node(5, root.right);
root.right.right.right = new Node(8, root.right.right);
root.right.right.right.right = new Node(12, root.right.right.right);
// passing 10
Console.WriteLine(findRightSibling(root.left.left.left.left, 0).data);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript program to print right sibling of a node
// A Binary Tree Node
class Node
{
constructor(data, parent) {
this.left = null;
this.right = null;
this.data = data;
this.parent = parent;
}
}
// Method to find right sibling
function findRightSibling(node, level)
{
if (node == null || node.parent == null)
return null;
// GET Parent pointer whose right child is not
// a parent or itself of this node. There might
// be case when parent has no right child, but,
// current node is left child of the parent
// (second condition is for that).
while (node.parent.right == node
|| (node.parent.right == null
&& node.parent.left == node)) {
if (node.parent == null)
return null;
node = node.parent;
level--;
}
// Move to the required child, where right sibling
// can be present
node = node.parent.right;
// find right sibling in the given subtree(from current
// node), when level will be 0
while (level < 0) {
// Iterate through subtree
if (node.left != null)
node = node.left;
else if (node.right != null)
node = node.right;
else
// if no child are there, we cannot have right
// sibling in this path
break;
level++;
}
if (level == 0)
return node;
// This is the case when we reach 9 node in the tree,
// where we need to again recursively find the right
// sibling
return findRightSibling(node, level);
}
let root = new Node(1, null);
root.left = new Node(2, root);
root.right = new Node(3, root);
root.left.left = new Node(4, root.left);
root.left.right = new Node(6, root.left);
root.left.left.left = new Node(7, root.left.left);
root.left.left.left.left = new Node(10, root.left.left.left);
root.left.right.right = new Node(9, root.left.right);
root.right.right = new Node(5, root.right);
root.right.right.right = new Node(8, root.right.right);
root.right.right.right.right = new Node(12, root.right.right.right);
// passing 10
document.write(findRightSibling(root.left.left.left.left, 0).data);
// This code is contributed by divyesh072019.
</script>
Producción
12
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Este artículo es una contribución de Krishna Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA