Escribe una función para conectar todos los Nodes adyacentes al mismo nivel en un árbol binario. La estructura del Node del árbol binario dado es como la siguiente.
C++
struct node {
int data;
struct node* left;
struct node* right;
struct node* nextRight;
}
C
struct node {
int data;
struct node* left;
struct node* right;
struct node* nextRight;
}
Python
class node: def __init__(self, data): self.data = data self.left = self.right = None self.nextRight = None # This code is contributed by vivekmaddheshiya205
Javascript
class node {
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
this.nextRight = null;
}
}
// This code is contributed by importantly.
Inicialmente, todos los punteros nextRight apuntan a valores basura. Su función debe configurar estos punteros para que apunten a la derecha de cada Node.
Ejemplo:
Input Tree
A
/ \
B C
/ \ \
D E F
Output Tree
A--->NULL
/ \
B-->C-->NULL
/ \ \
D-->E-->F-->NULL
Método 1 (Ampliar recorrido de orden de nivel o BFS):
Considere el método 2 de Level Order Traversal . El método 2 se puede ampliar fácilmente para conectar Nodes del mismo nivel. Podemos aumentar las entradas de la cola para que contengan el nivel de los Nodes, que también es 0 para root, 1 para los hijos de root, etc. Entonces, un Node de cola ahora contendrá un puntero a un Node de árbol y un nivel entero. Cuando ponemos en cola un Node, nos aseguramos de que el valor de nivel correcto para el Node se establezca en la cola. Para establecer nextRight, para cada Node N, sacamos el siguiente Node de la cola, si el número de nivel del siguiente Node es el mismo, establecemos nextRight of N como dirección del Node eliminado, de lo contrario, establecemos nextRight of N como NULL.
Inicializamos un Node Prev que apunta al Node anterior. Mientras recorremos los Nodes en el mismo nivel, hacemos un seguimiento del Node anterior y apuntamos el puntero nextRight al Node actual en cada iteración.
C++
/* Iterative program to connect all the adjacent nodes at the same level in a binary tree*/
#include <iostream>
#include<queue>
using namespace std;
// A Binary Tree Node
class node {
public:
int data;
node* left;
node* right;
node* nextRight;
/* Constructor that allocates a new node with the
given data and NULL left and right pointers. */
node(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
this->nextRight = NULL;
}
};
// setting right pointer to next right node
/*
10 ----------> NULL
/ \
8 --->2 --------> NULL
/
3 ----------------> NULL
*/
void connect(node *root)
{
//Base condition
if(root==NULL)
return;
// Create an empty queue like level order traversal
queue<node*> q;
q.push(root);
while(!q.empty()){
// size indicates no. of nodes at current level
int size=q.size();
// for keeping track of previous node
node* prev=NULL;
while(size--){
node* temp=q.front();
q.pop();
if(temp->left)
q.push(temp->left);
if(temp->right)
q.push(temp->right);
if(prev!=NULL)
prev->nextRight=temp;
prev=temp;
}
prev->nextRight=NULL;
}
}
int main() {
/* Constructed binary tree is
10
/ \
8 2
/
3
*/
// Let us create binary tree shown above
node* root = new node(10);
root->left = new node(8);
root->right = new node(2);
root->left->left = new node(3);
connect(root);
// Let us check the values
// of nextRight pointers
cout << "Following are populated nextRight pointers in the tree"
" (-1 is printed if there is no nextRight)\n";
cout << "nextRight of " << root->data << " is "
<< (root->nextRight ? root->nextRight->data : -1) << endl;
cout << "nextRight of " << root->left->data << " is "
<< (root->left->nextRight ? root->left->nextRight->data : -1) << endl;
cout << "nextRight of " << root->right->data << " is "
<< (root->right->nextRight ? root->right->nextRight->data : -1) << endl;
cout << "nextRight of " << root->left->left->data << " is "
<< (root->left->left->nextRight ? root->left->left->nextRight->data : -1) << endl;
return 0;
}
// this code is contributed by Kapil Poonia
Java
import java.util.*;
import java.io.*;
class Node {
int data;
Node left, right, nextRight;
Node(int item)
{
data = item;
left = right = nextRight = null;
}
}
public class BinaryTree {
Node root;
void connect(Node p)
{
// initialize queue to hold nodes at same level
Queue<Node> q = new LinkedList<>();
q.add(root); // adding nodes to the queue
Node temp = null; // initializing prev to null
while (!q.isEmpty()) {
int n = q.size();
for (int i = 0; i < n; i++) {
Node prev = temp;
temp = q.poll();
// i > 0 because when i is 0 prev points
// the last node of previous level,
// so we skip it
if (i > 0)
prev.nextRight = temp;
if (temp.left != null)
q.add(temp.left);
if (temp.right != null)
q.add(temp.right);
}
// pointing last node of the nth level to null
temp.nextRight = null;
}
}
// Driver program to test above functions
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
/* Constructed binary tree is
10
/ \
8 2
/
3
*/
tree.root = new Node(10);
tree.root.left = new Node(8);
tree.root.right = new Node(2);
tree.root.left.left = new Node(3);
// Populates nextRight pointer in all nodes
tree.connect(tree.root);
// Let us check the values of nextRight pointers
System.out.println("Following are populated nextRight pointers in "
+ "the tree"
+ "(-1 is printed if there is no nextRight)");
int a = tree.root.nextRight != null ? tree.root.nextRight.data : -1;
System.out.println("nextRight of " + tree.root.data + " is "
+ a);
int b = tree.root.left.nextRight != null ? tree.root.left.nextRight.data : -1;
System.out.println("nextRight of " + tree.root.left.data + " is "
+ b);
int c = tree.root.right.nextRight != null ? tree.root.right.nextRight.data : -1;
System.out.println("nextRight of " + tree.root.right.data + " is "
+ c);
int d = tree.root.left.left.nextRight != null ? tree.root.left.left.nextRight.data : -1;
System.out.println("nextRight of " + tree.root.left.left.data + " is "
+ d);
}
}
// This code has been contributed by Rahul Shakya
Python3
# Iterative program to connect all the adjacent nodes at the same level in a binary tree
class newnode:
def __init__(self, data):
self.data = data
self.left = self.right = self.nextRight = None
# setting right pointer to next right node
# 10 ----------> NULL
# / \
# 8 --->2 --------> NULL
# /
# 3 ----------------> NULL
def connect(root):
# Base condition
if root is None:
return
# Create an empty queue like level order traversal
queue = []
queue.append(root)
while len(queue) != 0:
# size indicates no. of nodes at current level
size = len(queue)
# for keeping track of previous node
prev = newnode(None)
for i in range(size):
temp = queue.pop(0)
if temp.left:
queue.append(temp.left)
if temp.right:
queue.append(temp.right)
if prev != None:
prev.nextRight = temp
prev = temp
prev.nextRight = None
# Driver Code
if __name__ == '__main__':
# Constructed binary tree is
# 10
# / \
# 8 2
# /
# 3
root = newnode(10)
root.left = newnode(8)
root.right = newnode(2)
root.left.left = newnode(3)
# Populates nextRight pointer in all nodes
connect(root)
# Let us check the values of nextRight pointers
print("Following are populated nextRight",
"pointers in the tree (-1 is printed",
"if there is no nextRight)")
print("nextRight of", root.data, "is ", end="")
if root.nextRight:
print(root.nextRight.data)
else:
print(-1)
print("nextRight of", root.left.data, "is ", end="")
if root.left.nextRight:
print(root.left.nextRight.data)
else:
print(-1)
print("nextRight of", root.right.data, "is ", end="")
if root.right.nextRight:
print(root.right.nextRight.data)
else:
print(-1)
print("nextRight of", root.left.left.data, "is ", end="")
if root.left.left.nextRight:
print(root.left.left.nextRight.data)
else:
print(-1)
# This code is contributed by Vivek Maddeshiya
C#
// C# program to connect nodes
// at same level
using System;
using System.Collections.Generic;
class Node
{
public int data;
public Node left, right, nextRight;
public Node(int item)
{
data = item;
left = right = nextRight = null;
}
}
public class BinaryTree
{
Node root;
void connect(Node p)
{
// initialize queue to hold nodes at same level
Queue<Node> q = new Queue<Node>();
q.Enqueue(root); // adding nodes to tehe queue
Node temp = null; // initializing prev to null
while (q.Count > 0)
{
int n = q.Count;
for (int i = 0; i < n; i++)
{
Node prev = temp;
temp = q.Dequeue();
// i > 0 because when i is 0 prev points
// the last node of previous level,
// so we skip it
if (i > 0)
prev.nextRight = temp;
if (temp.left != null)
q.Enqueue(temp.left);
if (temp.right != null)
q.Enqueue(temp.right);
}
// pointing last node of the nth level to null
temp.nextRight = null;
}
}
// Driver code
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/* Constructed binary tree is
10
/ \
8 2
/
3
*/
tree.root = new Node(10);
tree.root.left = new Node(8);
tree.root.right = new Node(2);
tree.root.left.left = new Node(3);
// Populates nextRight pointer in all nodes
tree.connect(tree.root);
// Let us check the values of nextRight pointers
Console.WriteLine("Following are populated nextRight pointers in "
+ "the tree"
+ "(-1 is printed if there is no nextRight)");
int a = tree.root.nextRight != null ? tree.root.nextRight.data : -1;
Console.WriteLine("nextRight of " + tree.root.data + " is "
+ a);
int b = tree.root.left.nextRight != null ? tree.root.left.nextRight.data : -1;
Console.WriteLine("nextRight of " + tree.root.left.data + " is "
+ b);
int c = tree.root.right.nextRight != null ? tree.root.right.nextRight.data : -1;
Console.WriteLine("nextRight of " + tree.root.right.data + " is "
+ c);
int d = tree.root.left.left.nextRight != null ? tree.root.left.left.nextRight.data : -1;
Console.WriteLine("nextRight of " + tree.root.left.left.data + " is "
+ d);
Console.ReadKey();
}
}
// This code has been contributed by techno2mahi
Javascript
<script>
class Node
{
constructor(item)
{
this.data = item;
this.left = this.right = this.nextRight = null;
}
}
let root;
function connect(p)
{
// initialize queue to hold nodes at same level
let q = [];
q.push(root); // adding nodes to the queue
let temp = null; // initializing prev to null
while (q.length!=0) {
let n = q.length;
for (let i = 0; i < n; i++) {
let prev = temp;
temp = q.shift();
// i > 0 because when i is 0 prev points
// the last node of previous level,
// so we skip it
if (i > 0)
prev.nextRight = temp;
if (temp.left != null)
q.push(temp.left);
if (temp.right != null)
q.push(temp.right);
}
// pointing last node of the nth level to null
temp.nextRight = null;
}
}
// Driver program to test above functions
/* Constructed binary tree is
10
/ \
8 2
/
3
*/
root = new Node(10);
root.left = new Node(8);
root.right = new Node(2);
root.left.left = new Node(3);
// Populates nextRight pointer in all nodes
connect(root);
// Let us check the values of nextRight pointers
document.write("Following are populated nextRight pointers in "
+ "the tree"
+ "(-1 is printed if there is no nextRight)<br>");
let a = root.nextRight != null ? root.nextRight.data : -1;
document.write("nextRight of " + root.data + " is "
+ a+"<br>");
let b = root.left.nextRight != null ? root.left.nextRight.data : -1;
document.write("nextRight of " + root.left.data + " is "
+ b+"<br>");
let c = root.right.nextRight != null ? root.right.nextRight.data : -1;
document.write("nextRight of " + root.right.data + " is "
+ c+"<br>");
let d = root.left.left.nextRight != null ? root.left.left.nextRight.data : -1;
document.write("nextRight of " + root.left.left.data + " is "
+ d+"<br>");
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Following are populated nextRight pointers in the tree (-1 is printed if there is no nextRight) nextRight of 10 is -1 nextRight of 8 is 2 nextRight of 2 is -1 nextRight of 3 is -1
Consulte conectar Nodes en el mismo nivel (transversal de orden de nivel) para la implementación.
Complejidad de tiempo: O(n)
Complejidad espacial: O(n)
Método 2 (Ampliar recorrido previo al pedido) :
Este enfoque solo funciona para árboles binarios completos . En este método, establecemos nextRight en modo Pre Order para asegurarnos de que nextRight del padre se establezca antes que sus hijos. Cuando estamos en el Node p, establecemos el nextRight de sus hijos izquierdo y derecho. Dado que el árbol es un árbol completo, nextRight del hijo izquierdo de p (p->left->nextRight) siempre será el hijo derecho de p, y nextRight del hijo derecho de p (p->right->nextRight) siempre será el hijo izquierdo de p nextRight (si p no es el Node más a la derecha en su nivel). Si p es el Node más a la derecha, nextRight del hijo derecho de p será NULL.
C++
// CPP program to connect nodes
// at same level using extended
// pre-order traversal
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
node* nextRight;
/* Constructor that allocates a new node with the
given data and NULL left and right pointers. */
node(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
this->nextRight = NULL;
}
};
void connectRecur(node* p);
// Sets the nextRight of
// root and calls connectRecur()
// for other nodes
void connect(node* p)
{
// Set the nextRight for root
p->nextRight = NULL;
// Set the next right for rest of the nodes
// (other than root)
connectRecur(p);
}
/* Set next right of all descendants of p.
Assumption: p is a complete binary tree */
void connectRecur(node* p)
{
// Base case
if (!p)
return;
// Set the nextRight pointer for p's left child
if (p->left)
p->left->nextRight = p->right;
// Set the nextRight pointer
// for p's right child p->nextRight
// will be NULL if p is the right
// most child at its level
if (p->right)
p->right->nextRight = (p->nextRight) ? p->nextRight->left : NULL;
// Set nextRight for other
// nodes in pre order fashion
connectRecur(p->left);
connectRecur(p->right);
}
/* Driver code*/
int main()
{
/* Constructed binary tree is
10
/ \
8 2
/
3
*/
node* root = new node(10);
root->left = new node(8);
root->right = new node(2);
root->left->left = new node(3);
// Populates nextRight pointer in all nodes
connect(root);
// Let us check the values
// of nextRight pointers
cout << "Following are populated nextRight pointers in the tree"
" (-1 is printed if there is no nextRight)\n";
cout << "nextRight of " << root->data << " is "
<< (root->nextRight ? root->nextRight->data : -1) << endl;
cout << "nextRight of " << root->left->data << " is "
<< (root->left->nextRight ? root->left->nextRight->data : -1) << endl;
cout << "nextRight of " << root->right->data << " is "
<< (root->right->nextRight ? root->right->nextRight->data : -1) << endl;
cout << "nextRight of " << root->left->left->data << " is "
<< (root->left->left->nextRight ? root->left->left->nextRight->data : -1) << endl;
return 0;
}
// This code is contributed by rathbhupendra
C
// C program to connect nodes at same level using extended
// pre-order traversal
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* left;
struct node* right;
struct node* nextRight;
};
void connectRecur(struct node* p);
// Sets the nextRight of root and calls connectRecur()
// for other nodes
void connect(struct node* p)
{
// Set the nextRight for root
p->nextRight = NULL;
// Set the next right for rest of the nodes
// (other than root)
connectRecur(p);
}
/* Set next right of all descendants of p.
Assumption: p is a complete binary tree */
void connectRecur(struct node* p)
{
// Base case
if (!p)
return;
// Set the nextRight pointer for p's left child
if (p->left)
p->left->nextRight = p->right;
// Set the nextRight pointer for p's right child
// p->nextRight will be NULL if p is the right
// most child at its level
if (p->right)
p->right->nextRight = (p->nextRight) ? p->nextRight->left : NULL;
// Set nextRight for other nodes in pre order fashion
connectRecur(p->left);
connectRecur(p->right);
}
/* UTILITY FUNCTIONS */
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newnode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
node->nextRight = NULL;
return (node);
}
/* Driver program to test above functions*/
int main()
{
/* Constructed binary tree is
10
/ \
8 2
/
3
*/
struct node* root = newnode(10);
root->left = newnode(8);
root->right = newnode(2);
root->left->left = newnode(3);
// Populates nextRight pointer in all nodes
connect(root);
// Let us check the values of nextRight pointers
printf("Following are populated nextRight pointers in the tree "
"(-1 is printed if there is no nextRight) \n");
printf("nextRight of %d is %d \n", root->data,
root->nextRight ? root->nextRight->data : -1);
printf("nextRight of %d is %d \n", root->left->data,
root->left->nextRight ? root->left->nextRight->data : -1);
printf("nextRight of %d is %d \n", root->right->data,
root->right->nextRight ? root->right->nextRight->data : -1);
printf("nextRight of %d is %d \n", root->left->left->data,
root->left->left->nextRight ? root->left->left->nextRight->data : -1);
return 0;
}
Java
// JAVA program to connect nodes
// at same level using extended
// pre-order traversal
import java.util.*;
class GFG {
static class node {
int data;
node left;
node right;
node nextRight;
/*
* Constructor that allocates a new node with the given data and null left and
* right pointers.
*/
node(int data) {
this.data = data;
this.left = null;
this.right = null;
this.nextRight = null;
}
};
// Sets the nextRight of
// root and calls connectRecur()
// for other nodes
static void connect(node p) {
// Set the nextRight for root
p.nextRight = null;
// Set the next right for rest of the nodes
// (other than root)
connectRecur(p);
}
/*
* Set next right of all descendants of p. Assumption: p is a complete binary
* tree
*/
static void connectRecur(node p) {
// Base case
if (p == null)
return;
// Set the nextRight pointer for p's left child
if (p.left != null)
p.left.nextRight = p.right;
// Set the nextRight pointer
// for p's right child p.nextRight
// will be null if p is the right
// most child at its level
if (p.right != null)
p.right.nextRight = (p.nextRight) != null ? p.nextRight.left : null;
// Set nextRight for other
// nodes in pre order fashion
connectRecur(p.left);
connectRecur(p.right);
}
/* Driver code */
public static void main(String[] args) {
/*
* Constructed binary tree is 10 / \ 8 2 / 3
*/
node root = new node(10);
root.left = new node(8);
root.right = new node(2);
root.left.left = new node(3);
// Populates nextRight pointer in all nodes
connect(root);
// Let us check the values
// of nextRight pointers
System.out.print("Following are populated nextRight pointers in the tree"
+ " (-1 is printed if there is no nextRight)\n");
System.out.print(
"nextRight of " + root.data + " is " + (root.nextRight != null ? root.nextRight.data : -1) + "\n");
System.out.print("nextRight of " + root.left.data + " is "
+ (root.left.nextRight != null ? root.left.nextRight.data : -1) + "\n");
System.out.print("nextRight of " + root.right.data + " is "
+ (root.right.nextRight != null ? root.right.nextRight.data : -1) + "\n");
System.out.print("nextRight of " + root.left.left.data + " is "
+ (root.left.left.nextRight != null ? root.left.left.nextRight.data : -1) + "\n");
}
}
// This code is contributed by umadevi9616
Python3
# Python3 program to connect nodes at same
# level using extended pre-order traversal
class newnode:
def __init__(self, data):
self.data = data
self.left = self.right = self.nextRight = None
# Sets the nextRight of root and calls
# connectRecur() for other nodes
def connect (p):
# Set the nextRight for root
p.nextRight = None
# Set the next right for rest of
# the nodes (other than root)
connectRecur(p)
# Set next right of all descendants of p.
# Assumption: p is a complete binary tree
def connectRecur(p):
# Base case
if (not p):
return
# Set the nextRight pointer for p's
# left child
if (p.left):
p.left.nextRight = p.right
# Set the nextRight pointer for p's right
# child p.nextRight will be None if p is
# the right most child at its level
if (p.right):
if p.nextRight:
p.right.nextRight = p.nextRight.left
else:
p.right.nextRight = None
# Set nextRight for other nodes in
# pre order fashion
connectRecur(p.left)
connectRecur(p.right)
# Driver Code
if __name__ == '__main__':
# Constructed binary tree is
# 10
# / \
# 8 2
# /
# 3
root = newnode(10)
root.left = newnode(8)
root.right = newnode(2)
root.left.left = newnode(3)
# Populates nextRight pointer in all nodes
connect(root)
# Let us check the values of nextRight pointers
print("Following are populated nextRight",
"pointers in the tree (-1 is printed",
"if there is no nextRight)")
print("nextRight of", root.data, "is ", end = "")
if root.nextRight:
print(root.nextRight.data)
else:
print(-1)
print("nextRight of", root.left.data, "is ", end = "")
if root.left.nextRight:
print(root.left.nextRight.data)
else:
print(-1)
print("nextRight of", root.right.data, "is ", end = "")
if root.right.nextRight:
print(root.right.nextRight.data)
else:
print(-1)
print("nextRight of", root.left.left.data, "is ", end = "")
if root.left.left.nextRight:
print(root.left.left.nextRight.data)
else:
print(-1)
# This code is contributed by PranchalK
C#
using System;
// C# program to connect nodes at same level using extended
// pre-order traversal
// A binary tree node
public class Node {
public int data;
public Node left, right, nextRight;
public Node(int item)
{
data = item;
left = right = nextRight = null;
}
}
public class BinaryTree {
public Node root;
// Sets the nextRight of root and calls connectRecur()
// for other nodes
public virtual void connect(Node p)
{
// Set the nextRight for root
p.nextRight = null;
// Set the next right for rest of the nodes (other
// than root)
connectRecur(p);
}
/* Set next right of all descendants of p.
Assumption: p is a complete binary tree */
public virtual void connectRecur(Node p)
{
// Base case
if (p == null) {
return;
}
// Set the nextRight pointer for p's left child
if (p.left != null) {
p.left.nextRight = p.right;
}
// Set the nextRight pointer for p's right child
// p->nextRight will be NULL if p is the right most child
// at its level
if (p.right != null) {
p.right.nextRight = (p.nextRight != null) ? p.nextRight.left : null;
}
// Set nextRight for other nodes in pre order fashion
connectRecur(p.left);
connectRecur(p.right);
}
// Driver program to test above functions
public static void Main(string[] args)
{
BinaryTree tree = new BinaryTree();
/* Constructed binary tree is
10
/ \
8 2
/
3
*/
tree.root = new Node(10);
tree.root.left = new Node(8);
tree.root.right = new Node(2);
tree.root.left.left = new Node(3);
// Populates nextRight pointer in all nodes
tree.connect(tree.root);
// Let us check the values of nextRight pointers
Console.WriteLine("Following are populated nextRight pointers in "
+ "the tree"
+ "(-1 is printed if there is no nextRight)");
int a = tree.root.nextRight != null ? tree.root.nextRight.data : -1;
Console.WriteLine("nextRight of " + tree.root.data + " is " + a);
int b = tree.root.left.nextRight != null ? tree.root.left.nextRight.data : -1;
Console.WriteLine("nextRight of " + tree.root.left.data + " is " + b);
int c = tree.root.right.nextRight != null ? tree.root.right.nextRight.data : -1;
Console.WriteLine("nextRight of " + tree.root.right.data + " is " + c);
int d = tree.root.left.left.nextRight != null ? tree.root.left.left.nextRight.data : -1;
Console.WriteLine("nextRight of " + tree.root.left.left.data + " is " + d);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript program to connect nodes
// at same level using extended
// pre-order traversal
class Node
{
constructor(item)
{
this.data = item;
this.left = this.right = this.nextRight = null;
}
}
// Sets the nextRight of
// root and calls connectRecur()
// for other nodes
function connect( p) {
// Set the nextRight for root
p.nextRight = null;
// Set the next right for rest of the nodes
// (other than root)
connectRecur(p);
}
/*
* Set next right of all descendants of p. Assumption: p is a complete binary
* tree
*/
function connectRecur( p) {
// Base case
if (p == null)
return;
// Set the nextRight pointer for p's left child
if (p.left != null)
p.left.nextRight = p.right;
// Set the nextRight pointer
// for p's right child p.nextRight
// will be null if p is the right
// most child at its level
if (p.right != null)
p.right.nextRight = (p.nextRight) != null ? p.nextRight.left : null;
// Set nextRight for other
// nodes in pre order fashion
connectRecur(p.left);
connectRecur(p.right);
}
// Driver program to test above functions
/* Constructed binary tree is
10
/ \
8 2
/
3
*/
let root = new Node(10);
root.left = new Node(8);
root.right = new Node(2);
root.left.left = new Node(3);
// Populates nextRight pointer in all nodes
connect(root);
// Let us check the values of nextRight pointers
document.write("Following are populated nextRight pointers in "
+ "the tree"
+ "(-1 is printed if there is no nextRight)<br>");
let a = root.nextRight != null ? root.nextRight.data : -1;
document.write("nextRight of " + root.data + " is "
+ a+"<br>");
let b = root.left.nextRight != null ? root.left.nextRight.data : -1;
document.write("nextRight of " + root.left.data + " is "
+ b+"<br>");
let c = root.right.nextRight != null ? root.right.nextRight.data : -1;
document.write("nextRight of " + root.right.data + " is "
+ c+"<br>");
let d = root.left.left.nextRight != null ? root.left.left.nextRight.data : -1;
document.write("nextRight of " + root.left.left.data + " is "
+ d+"<br>");
// This code is contributed by jana_sayantan.
</script>
Producción:
Following are populated nextRight pointers in the tree (-1 is printed if there is no nextRight) nextRight of 10 is -1 nextRight of 8 is 2 nextRight of 2 is -1 nextRight of 3 is -1
Gracias a Dhanya por sugerir este enfoque.
Complejidad de tiempo: O(n)
Complejidad espacial: O(n)
¿Por qué el método 2 no funciona para árboles que no son árboles binarios completos?
Consideremos el siguiente árbol como ejemplo. En el Método 2, configuramos el puntero nextRight en forma de pedido previo. Cuando estamos en el Node 4, establecemos el nextRight de sus hijos que son 8 y 9 (el nextRight de 4 ya está establecido como Node 5). nextRight de 8 simplemente se establecerá como 9, pero nextRight de 9 se establecerá como NULL, lo cual es incorrecto. No podemos establecer el nextRight correcto, porque cuando establecemos nextRight de 9, solo tenemos nextRight del Node 4 y los ancestros del Node 4, no tenemos nextRight de los Nodes en el subárbol derecho de la raíz.
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \
8 9 10 11
Consulte Conectar Nodes al mismo nivel usando espacio adicional constante para obtener más soluciones.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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