Conecte Nodes al mismo nivel utilizando espacio extra constante

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;
}

Java

static class node {
  int data;
  node left;
  node right;
  node nextRight;
}
  
// This code is contributed by umadevi9616 

Python3

class newnode:
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None
        self.nextRight = None
          
# this code is contributed by shivanisinghss2110

C#

public class Node
{
    public int data;
    public Node left;
    public Node right;
    public Node nextRight;
}
  
// this code is contributed by shivanisinghss2110

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. Solo puede usar espacio adicional constante.

C

// Recursive C program to connect nodes at same level
// using constant extra space
void connectRecur(struct node* p);
struct node *getNextRight(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.
   This function makes sure that
   nextRight of nodes ar level i is set 
   before level i+1 nodes. */
void connectRecur(struct node* p)
{
    // Base case
    if (!p)
       return;
  
    /* Before setting nextRight of left and right 
       children, set nextRight of children of other
       nodes at same level (because we can access 
       children of other nodes using p's nextRight only) */
    if (p->nextRight != NULL)
       connectRecur(p->nextRight);
  
    /* Set the nextRight pointer for p's left child */
    if (p->left)
    {
       if (p->right)
       {
           p->left->nextRight = p->right;
           p->right->nextRight = getNextRight(p);
       }
       else
           p->left->nextRight = getNextRight(p);
  
       /* Recursively call for next level nodes. 
          Note that we call only for left child.
          The call for left child will call for right child */
       connectRecur(p->left);
    }
  
    /* If left child is NULL then first node of
       next level will either be
       p->right or getNextRight(p) */
    else if (p->right)
    {
        p->right->nextRight = getNextRight(p);
        connectRecur(p->right);
    }
    else
       connectRecur(getNextRight(p));
}
  
/* This function returns the leftmost child of nodes
   at the same level as p. This function is used to 
   getNExt right of p's right child If right child 
   of p is NULL then this can also be used for the left child */
struct node *getNextRight(struct node *p)
{
    struct node *temp = p->nextRight;
  
    /* Traverse nodes at p's level and find and return
       the first node's first child */
    while(temp != NULL)
    {
        if(temp->left != NULL)
            return temp->left;
        if(temp->right != NULL)
            return temp->right;
        temp = temp->nextRight;
    }
  
    // If all the nodes at p's level are leaf 
    // nodes then return NULL
    return NULL;
}

Java

// Recursive Java program to connect nodes at same level
// using constant extra space
   
// A binary tree node
class Node 
{
    int data;
    Node left, right, nextRight;
   
    Node(int item) 
    {
        data = item;
        left = right = nextRight = null;
    }
}
   
class BinaryTree 
{
    Node root;
   
    /* Set next right of all descendants of p. This function makes sure that
       nextRight of nodes ar level i is set before level i+1 nodes. */
    void connectRecur(Node p) 
    {
        // Base case
        if (p == null)
            return;
   
        /* Before setting nextRight of left and right children, set nextRight
           of children of other nodes at same level (because we can access 
           children of other nodes using p's nextRight only) */
        if (p.nextRight != null)
            connectRecur(p.nextRight);
   
        /* Set the nextRight pointer for p's left child */
        if (p.left != null)
        {
            if (p.right != null) 
            {
                p.left.nextRight = p.right;
                p.right.nextRight = getNextRight(p);
            } 
            else
                p.left.nextRight = getNextRight(p);
   
            /* Recursively call for next level nodes.  Note that we call only
             for left child. The call for left child will call for right child */
            connectRecur(p.left);
        }
           
        /* If left child is NULL then first node of next level will either be
         p->right or getNextRight(p) */
        else if (p.right != null) 
        {
            p.right.nextRight = getNextRight(p);
            connectRecur(p.right);
        } 
        else
            connectRecur(getNextRight(p));
    }
   
    /* This function returns the leftmost child of nodes at the same
       level as p. This function is used to getNExt right of p's right child
       If right child of p is NULL then this can also be used for 
       the left child */
    Node getNextRight(Node p) 
    {
        Node temp = p.nextRight;
   
        /* Traverse nodes at p's level and find and return
         the first node's first child */
        while (temp != null) 
        {
            if (temp.left != null)
                return temp.left;
            if (temp.right != null)
                return temp.right;
            temp = temp.nextRight;
        }
   
        // If all the nodes at p's level are leaf nodes then return NULL
        return null;
    }
   
    /* Driver program to test the above functions */
    public static void main(String args[]) 
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(10);
        tree.root.left = new Node(8);
        tree.root.right = new Node(2);
        tree.root.left.left = new Node(3);
        tree.root.right.right = new Node(90);
   
        // Populates nextRight pointer in all nodes
        tree.connectRecur(tree.root);
   
        // Let us check the values of nextRight pointers
        int a = tree.root.nextRight != null ? 
                          tree.root.nextRight.data : -1;
        int b = tree.root.left.nextRight != null ? 
                          tree.root.left.nextRight.data : -1;
        int c = tree.root.right.nextRight != null ?
                            tree.root.right.nextRight.data : -1;
        int d = tree.root.left.left.nextRight != null ?
                        tree.root.left.left.nextRight.data : -1;
        int e = tree.root.right.right.nextRight != null ? 
                        tree.root.right.right.nextRight.data : -1;
           
        // Now lets print the values
        System.out.println("Following are populated nextRight pointers in "
                + " the tree(-1 is printed if there is no nextRight)");
        System.out.println("nextRight of " + tree.root.data + " is " + a);
        System.out.println("nextRight of " + tree.root.left.data + " is " + b);
        System.out.println("nextRight of " + tree.root.right.data + " is " + c);
        System.out.println("nextRight of " + tree.root.left.left.data + 
                                                              " is " + d);
        System.out.println("nextRight of " + tree.root.right.right.data + 
                                                              " is " + e);
    }
}
  
// This code has been contributed by Mayank Jaiswal

Python3

# Recursive Python program to connect nodes
# at same level using constant extra space
  
# Helper class that allocates a new node
# with the given data and None left and
# right pointers.
class newnode:
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None
        self.nextRight = None
          
  
# Set next right of all descendants of p. This function makes sure that
# nextRight of nodes ar level i is set before level i+1 nodes. */
def connectRecur( p) :
      
    # Base case
    if p == None :
        return
    
    # Before setting nextRight of left and right children, set nextRight
    # of children of other nodes at same level (because we can access
    # children of other nodes using p's nextRight only) */
    if p.nextRight != None :
        connectRecur(p.nextRight)
    
    # Set the nextRight pointer for p's left child */
    if p.left != None :
          
        if p.right != None :
              
            p.left.nextRight = p.right
            p.right.nextRight = getNextRight(p)
              
        else :
            p.left.nextRight = getNextRight(p)
    
        # Recursively call for next level nodes.  Note that we call only
        # for left child. The call for left child will call for right child */
        connectRecur(p.left)
          
            
        # If left child is NULL then first node of next level will either be
        # p->right or getNextRight(p) */
    elif p.right != None :
          
        p.right.nextRight = getNextRight(p)
        connectRecur(p.right)
          
    else :
        connectRecur(getNextRight(p))
  
    
    
# This function returns the leftmost child of
# nodes at the same level as p. This function
# is used to getNExt right of p's right child
# If right child of is None then this can also
# be used for the left child
def getNextRight(p):
    temp = p.nextRight
  
    # Traverse nodes at p's level and find
    # and return the first node's first child
    while (temp != None):
        if (temp.left != None):
            return temp.left
        if (temp.right != None):
            return temp.right
        temp = temp.nextRight
  
    # If all the nodes at p's level are
    # leaf nodes then return None
    return None
  
# Driver Code
if __name__ == '__main__':
  
    # Constructed binary tree is
    #         10
    #     / \
    #     8     2
    # /         \
    # 3         90
    root = newnode(10)
    root.left     = newnode(8)
    root.right     = newnode(2)
    root.left.left = newnode(3)
    root.right.right     = newnode(90)
  
    # Populates nextRight pointer in all nodes
    connectRecur(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) \n")
    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)
    print("nextRight of", root.right.right.data,
                                "is", end = " ")
    if root.right.right.nextRight:
        print(root.right.right.nextRight.data)
    else:
        print(-1)
  
# This code is contributed by jana_sayantan.

C#

using System;
  
// Recursive C# program to connect nodes at same level 
// using constant extra space 
  
// 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;
  
    /* Set next right of all descendants of p. This function makes sure that 
       nextRight of nodes ar level i is set before level i+1 nodes. */
    public virtual void connectRecur(Node p)
    {
        // Base case 
        if (p == null)
        {
            return;
        }
  
        /* Before setting nextRight of left and right children, set nextRight 
           of children of other nodes at same level (because we can access  
           children of other nodes using p's nextRight only) */
        if (p.nextRight != null)
        {
            connectRecur(p.nextRight);
        }
  
        /* Set the nextRight pointer for p's left child */
        if (p.left != null)
        {
            if (p.right != null)
            {
                p.left.nextRight = p.right;
                p.right.nextRight = getNextRight(p);
            }
            else
            {
                p.left.nextRight = getNextRight(p);
            }
  
            /* Recursively call for next level nodes.  Note that we call only 
             for left child. The call for left child will call for right child */
            connectRecur(p.left);
        }
  
        /* If left child is NULL then first node of next level will either be 
         p->right or getNextRight(p) */
        else if (p.right != null)
        {
            p.right.nextRight = getNextRight(p);
            connectRecur(p.right);
        }
        else
        {
            connectRecur(getNextRight(p));
        }
    }
  
    /* This function returns the leftmost child of nodes at the same 
       level as p. This function is used to getNExt right of p's right child 
       If right child of p is NULL then this can also be used for  
       the left child */
    public virtual Node getNextRight(Node p)
    {
        Node temp = p.nextRight;
  
        /* Traverse nodes at p's level and find and return 
         the first node's first child */
        while (temp != null)
        {
            if (temp.left != null)
            {
                return temp.left;
            }
            if (temp.right != null)
            {
                return temp.right;
            }
            temp = temp.nextRight;
        }
  
        // If all the nodes at p's level are leaf nodes then return NULL 
        return null;
    }
  
    /* Driver program to test the above functions */
    public static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(10);
        tree.root.left = new Node(8);
        tree.root.right = new Node(2);
        tree.root.left.left = new Node(3);
        tree.root.right.right = new Node(90);
  
        // Populates nextRight pointer in all nodes 
        tree.connectRecur(tree.root);
  
        // Let us check the values of nextRight pointers 
        int a = tree.root.nextRight != null ? tree.root.nextRight.data : -1;
        int b = tree.root.left.nextRight != null ? tree.root.left.nextRight.data : -1;
        int c = tree.root.right.nextRight != null ? tree.root.right.nextRight.data : -1;
        int d = tree.root.left.left.nextRight != null ? tree.root.left.left.nextRight.data : -1;
        int e = tree.root.right.right.nextRight != null ? tree.root.right.right.nextRight.data : -1;
  
        // Now lets print the values 
        Console.WriteLine("Following are populated nextRight pointers in the tree(-1 is printed if there is no nextRight)");
        Console.WriteLine("nextRight of " + tree.root.data + " is " + a);
        Console.WriteLine("nextRight of " + tree.root.left.data + " is " + b);
        Console.WriteLine("nextRight of " + tree.root.right.data + " is " + c);
        Console.WriteLine("nextRight of " + tree.root.left.left.data + " is " + d);
        Console.WriteLine("nextRight of " + tree.root.right.right.data + " is " + e);
    }
}
  
  // This code is contributed by Shrikant13

Javascript

<script>
// Recursive javascript program to connect nodes at same level
// using constant extra space
   
// A binary tree node
class Node {
        constructor(val) {
            this.data = val;
            this.left = null;
            this.right = null;
            this.nextRight = null;
        }
    }
   
var root;
   
    /* Set next right of all descendants of p. This function makes sure that
       nextRight of nodes ar level i is set before level i+1 nodes. */
    function connectRecur(p) 
    {
        // Base case
        if (p == null)
            return;
   
        /* Before setting nextRight of left and right children, set nextRight
           of children of other nodes at same level (because we can access 
           children of other nodes using p's nextRight only) */
        if (p.nextRight != null)
            connectRecur(p.nextRight);
   
        /* Set the nextRight pointer for p's left child */
        if (p.left != null)
        {
            if (p.right != null) 
            {
                p.left.nextRight = p.right;
                p.right.nextRight = getNextRight(p);
            } 
            else
                p.left.nextRight = getNextRight(p);
   
            /* Recursively call for next level nodes.  Note that we call only
             for left child. The call for left child will call for right child */
            connectRecur(p.left);
        }
           
        /* If left child is NULL then first node of next level will either be
         p->right or getNextRight(p) */
        else if (p.right != null) 
        {
            p.right.nextRight = getNextRight(p);
            connectRecur(p.right);
        } 
        else
            connectRecur(getNextRight(p));
    }
   
    /* This function returns the leftmost child of nodes at the same
       level as p. This function is used to getNExt right of p's right child
       If right child of p is NULL then this can also be used for 
       the left child */
    function getNextRight(p) 
    {
        var temp = p.nextRight;
   
        /* Traverse nodes at p's level and find and return
         the first node's first child */
        while (temp != null) 
        {
            if (temp.left != null)
                return temp.left;
            if (temp.right != null)
                return temp.right;
            temp = temp.nextRight;
        }
   
        // If all the nodes at p's level are leaf nodes then return NULL
        return null;
    }
   
    /* Driver program to test the above functions */
  
        var root = new Node(10);
        root.left = new Node(8);
        root.right = new Node(2);
        root.left.left = new Node(3);
        root.right.right = new Node(90);
   
        // Populates nextRight pointer in all nodes
        connectRecur(root);
   
        // Let us check the values of nextRight pointers
        var a = root.nextRight != null ? 
                          root.nextRight.data : -1;
        var b = root.left.nextRight != null ? 
                          root.left.nextRight.data : -1;
        var c = root.right.nextRight != null ?
                            root.right.nextRight.data : -1;
        var d = root.left.left.nextRight != null ?
                        root.left.left.nextRight.data : -1;
        var e = root.right.right.nextRight != null ? 
                        root.right.right.nextRight.data : -1;
           
        // Now lets print the values
        document.write("Following are populated nextRight pointers in "
                + " the tree(-1 is printed if there is no nextRight)");
        document.write("<br/>nextRight of " + root.data + " is " + a);
        document.write("<br/>nextRight of " + root.left.data + " is " + b);
        document.write("<br/>nextRight of " + root.right.data + " is " + c);
        document.write("<br/>nextRight of " + root.left.left.data + 
                                                              " is " + d);
        document.write("<br/>nextRight of " + root.right.right.data + 
                                                              " is " + e);
  
// This code is contributed by umadevi9616 
</script>

C++

// Iterative CPP program to connect
// nodes at same level using
// constant extra space 
#include<bits/stdc++.h> 
#include<bits/stdc++.h>
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;
    }
}; 
  
/* This function returns the leftmost
child of nodes at the same level as p. 
This function is used to getNExt right
of p's right child  If right child of
is NULL then this can also be used for
the left child */
node *getNextRight(node *p) 
{ 
    node *temp = p->nextRight; 
  
    /* Traverse nodes at p's level
    and find and return the first 
    node's first child */
    while (temp != NULL) 
    { 
        if (temp->left != NULL) 
            return temp->left; 
        if (temp->right != NULL) 
            return temp->right; 
        temp = temp->nextRight; 
    } 
  
    // If all the nodes at p's level 
    // are leaf nodes then return NULL 
    return NULL; 
} 
  
/* Sets nextRight of all nodes
of a tree with root as p */
void connectRecur(node* p) 
{ 
    node *temp; 
  
    if (!p) 
    return; 
  
    // Set nextRight for root 
    p->nextRight = NULL; 
  
    // set nextRight of all levels one by one 
    while (p != NULL) 
    { 
        node *q = p; 
  
        /* Connect all children nodes of p and
        children nodes of all other nodes at
        same level as p */
        while (q != NULL) 
        { 
            // Set the nextRight pointer
            // for p's left child 
            if (q->left) 
            { 
                // If q has right child, then 
                // right child is nextRight of 
                // p and we also need to set
                // nextRight of right child 
                if (q->right) 
                    q->left->nextRight = q->right; 
                else
                    q->left->nextRight = getNextRight(q); 
            } 
  
            if (q->right) 
                q->right->nextRight = getNextRight(q); 
  
            // Set nextRight for other 
            // nodes in pre order fashion 
            q = q->nextRight; 
        } 
  
        // start from the first 
        // node of next level 
        if (p->left) 
            p = p->left; 
        else if (p->right) 
            p = p->right; 
        else
            p = getNextRight(p); 
    } 
} 
  
  
/* Driver code*/
int main() 
{ 
  
    /* Constructed binary tree is 
            10 
            / \ 
        8 2 
        /     \ 
    3     90 
    */
    node *root = new node(10); 
    root->left = new node(8); 
    root->right = new node(2); 
    root->left->left = new node(3); 
    root->right->right     = new node(90); 
  
    // Populates nextRight pointer in all nodes 
    connectRecur(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;
    cout << "nextRight of " << root->right->right->data << " is "
        << (root->right->right->nextRight? root->right->right->nextRight->data: -1) << endl;
    return 0; 
} 
  
// This code is contributed by rathbhupendra

C

// Iterative C program to connect nodes at same level
// using constant extra space
#include <stdio.h>
#include <stdlib.h>
  
struct node
{
    int data;
    struct node *left;
    struct node *right;
    struct node *nextRight;
};
  
/* This function returns the leftmost child of nodes at the same level as p.
   This function is used to getNExt right of p's right child
   If right child of is NULL then this can also be used for the left child */
struct node *getNextRight(struct node *p)
{
    struct node *temp = p->nextRight;
  
    /* Traverse nodes at p's level and find and return
       the first node's first child */
    while (temp != NULL)
    {
        if (temp->left != NULL)
            return temp->left;
        if (temp->right != NULL)
            return temp->right;
        temp = temp->nextRight;
    }
  
    // If all the nodes at p's level are leaf nodes then return NULL
    return NULL;
}
  
/* Sets nextRight of all nodes of a tree with root as p */
void connect(struct node* p)
{
    struct node *temp;
  
    if (!p)
      return;
  
    // Set nextRight for root
    p->nextRight = NULL;
  
    // set nextRight of all levels one by one
    while (p != NULL)
    {
        struct node *q = p;
  
        /* Connect all children nodes of p and children nodes of all other nodes
          at same level as p */
        while (q != NULL)
        {
            // Set the nextRight pointer for p's left child
            if (q->left)
            {
                // If q has right child, then right child is nextRight of
                // p and we also need to set nextRight of right child
                if (q->right)
                    q->left->nextRight = q->right;
                else
                    q->left->nextRight = getNextRight(q);
            }
  
            if (q->right)
                q->right->nextRight = getNextRight(q);
  
            // Set nextRight for other nodes in pre order fashion
            q = q->nextRight;
        }
  
        // start from the first node of next level
        if (p->left)
           p = p->left;
        else if (p->right)
           p = p->right;
        else
           p = getNextRight(p);
    }
}
  
/* 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            90
    */
    struct node *root = newnode(10);
    root->left        = newnode(8);
    root->right       = newnode(2);
    root->left->left  = newnode(3);
    root->right->right       = newnode(90);
  
    // 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);
    printf("nextRight of %d is %d \n", root->right->right->data,
           root->right->right->nextRight? root->right->right->nextRight->data: -1);
  
    getchar();
    return 0;
}

Java

// Iterative Java program to connect nodes at same level
// using constant extra space
   
// A binary tree node
class Node 
{
    int data;
    Node left, right, nextRight;
   
    Node(int item) 
    {
        data = item;
        left = right = nextRight = null;
    }
}
   
class BinaryTree 
{
    Node root;
   
    /* This function returns the leftmost child of nodes at the same level
       as p. This function is used to getNExt right of p's right child
       If right child of is NULL then this can also be used for the 
       left child */
    Node getNextRight(Node p) 
    {
        Node temp = p.nextRight;
   
        /* Traverse nodes at p's level and find and return
           the first node's first child */
        while (temp != null) 
        {
            if (temp.left != null)
                return temp.left;
            if (temp.right != null)
                return temp.right;
            temp = temp.nextRight;
        }
   
        // If all the nodes at p's level are leaf nodes then return NULL
        return null;
    }
   
    /* Sets nextRight of all nodes of a tree with root as p */
    void connect(Node p) {
        Node temp = null;
   
        if (p == null)
            return;
   
        // Set nextRight for root
        p.nextRight = null;
   
        // set nextRight of all levels one by one
        while (p != null) 
        {
            Node q = p;
   
            /* Connect all children nodes of p and children nodes of all other
               nodes at same level as p */
            while (q != null) 
            {
                // Set the nextRight pointer for p's left child
                if (q.left != null) 
                {
                   
                    // If q has right child, then right child is nextRight of
                    // p and we also need to set nextRight of right child
                    if (q.right != null)
                        q.left.nextRight = q.right;
                    else
                        q.left.nextRight = getNextRight(q);
                }
   
                if (q.right != null)
                    q.right.nextRight = getNextRight(q);
   
                // Set nextRight for other nodes in pre order fashion
                q = q.nextRight;
            }
   
            // start from the first node of next level
            if (p.left != null)
                p = p.left;
            else if (p.right != null)
                p = p.right;
            else
                p = getNextRight(p);
        }
    }
      
    /* Driver program to test above functions */
    public static void main(String args[]) 
    {
         /* Constructed binary tree is
                 10
               /   \
             8      2
           /         \
         3            90
        */
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(10);
        tree.root.left = new Node(8);
        tree.root.right = new Node(2);
        tree.root.left.left = new Node(3);
        tree.root.right.right = new Node(90);
   
        // Populates nextRight pointer in all nodes
        tree.connect(tree.root);
           
        // Let us check the values of nextRight pointers
        int a = tree.root.nextRight != null ? 
                                     tree.root.nextRight.data : -1;
        int b = tree.root.left.nextRight != null ? 
                                 tree.root.left.nextRight.data : -1;
        int c = tree.root.right.nextRight != null ? 
                                tree.root.right.nextRight.data : -1;
        int d = tree.root.left.left.nextRight != null ? 
                                  tree.root.left.left.nextRight.data : -1;
        int e = tree.root.right.right.nextRight != null ? 
                                   tree.root.right.right.nextRight.data : -1;
           
        // Now lets print the values
        System.out.println("Following are populated nextRight pointers in "
                + " the tree(-1 is printed if there is no nextRight)");
        System.out.println("nextRight of " + tree.root.data + " is " + a);
        System.out.println("nextRight of " + tree.root.left.data 
                                                       + " is " + b);
        System.out.println("nextRight of " + tree.root.right.data + 
                                                           " is " + c);
        System.out.println("nextRight of " + tree.root.left.left.data + 
                                                            " is " + d);
        System.out.println("nextRight of " + tree.root.right.right.data + 
                                                             " is " + e);
    }
}
  
// This code has been contributed by Mayank Jaiswal

Python3

# Iterative Python program to connect nodes 
# at same level using constant extra space 
  
# Helper class that allocates a new node 
# with the given data and None left and 
# right pointers. 
class newnode:
    def __init__(self,data):
        self.data = data 
        self.left = None
        self.right = None
        self.nextRight = None
          
# This function returns the leftmost child of  
# nodes at the same level as p. This function 
# is used to getNExt right of p's right child 
# If right child of is None then this can also
# be used for the left child 
def getNextRight(p):
    temp = p.nextRight 
  
    # Traverse nodes at p's level and find 
    # and return the first node's first child 
    while (temp != None):
        if (temp.left != None):
            return temp.left 
        if (temp.right != None): 
            return temp.right 
        temp = temp.nextRight
  
    # If all the nodes at p's level are 
    # leaf nodes then return None 
    return None
  
# Sets nextRight of all nodes of a tree 
# with root as p 
def connect(p):
    temp = None
  
    if (not p): 
        return
  
    # Set nextRight for root 
    p.nextRight = None
  
    # set nextRight of all levels one by one 
    while (p != None):
        q = p 
  
        # Connect all children nodes of p and 
        # children nodes of all other nodes 
        # at same level as p 
        while (q != None):
              
            # Set the nextRight pointer for 
            # p's left child 
            if (q.left):
                  
                # If q has right child, then right 
                # child is nextRight of p and we 
                # also need to set nextRight of 
                # right child 
                if (q.right): 
                    q.left.nextRight = q.right 
                else:
                    q.left.nextRight = getNextRight(q)
  
            if (q.right):
                q.right.nextRight = getNextRight(q) 
  
            # Set nextRight for other nodes in
            # pre order fashion 
            q = q.nextRight
  
        # start from the first node 
        # of next level 
        if (p.left):
            p = p.left 
        elif (p.right):
            p = p.right 
        else:
            p = getNextRight(p)
  
# Driver Code
if __name__ == '__main__':
  
    # Constructed binary tree is 
    #         10 
    #     / \ 
    #     8     2 
    # /         \ 
    # 3         90 
    root = newnode(10) 
    root.left     = newnode(8) 
    root.right     = newnode(2) 
    root.left.left = newnode(3) 
    root.right.right     = newnode(90) 
  
    # 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) \n") 
    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)
    print("nextRight of", root.right.right.data,
                                "is", end = " ") 
    if root.right.right.nextRight:
        print(root.right.right.nextRight.data)
    else:
        print(-1)
  
# This code is contributed by PranchalK

C#

using System;
  
// Iterative c# program to connect nodes at same level 
// using constant extra space 
  
// 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;
  
    /* This function returns the leftmost child of nodes at the same level 
       as p. This function is used to getNExt right of p's right child 
       If right child of is NULL then this can also be used for the  
       left child */
    public virtual Node getNextRight(Node p)
    {
        Node temp = p.nextRight;
  
        /* Traverse nodes at p's level and find and return 
           the first node's first child */
        while (temp != null)
        {
            if (temp.left != null)
            {
                return temp.left;
            }
            if (temp.right != null)
            {
                return temp.right;
            }
            temp = temp.nextRight;
        }
  
        // If all the nodes at p's level are leaf nodes then return NULL 
        return null;
    }
  
    /* Sets nextRight of all nodes of a tree with root as p */
    public virtual void connect(Node p)
    {
        Node temp = null;
  
        if (p == null)
        {
            return;
        }
  
        // Set nextRight for root 
        p.nextRight = null;
  
        // set nextRight of all levels one by one 
        while (p != null)
        {
            Node q = p;
  
            /* Connect all children nodes of p and children nodes of all other 
               nodes at same level as p */
            while (q != null)
            {
                // Set the nextRight pointer for p's left child 
                if (q.left != null)
                {
  
                    // If q has right child, then right child is nextRight of 
                    // p and we also need to set nextRight of right child 
                    if (q.right != null)
                    {
                        q.left.nextRight = q.right;
                    }
                    else
                    {
                        q.left.nextRight = getNextRight(q);
                    }
                }
  
                if (q.right != null)
                {
                    q.right.nextRight = getNextRight(q);
                }
  
                // Set nextRight for other nodes in pre order fashion 
                q = q.nextRight;
            }
  
            // start from the first node of next level 
            if (p.left != null)
            {
                p = p.left;
            }
            else if (p.right != null)
            {
                p = p.right;
            }
            else
            {
                p = getNextRight(p);
            }
        }
    }
  
    /* Driver program to test above functions */
    public static void Main(string[] args)
    {
         /* Constructed binary tree is 
                 10 
               /   \ 
             8      2 
           /         \ 
         3            90 
        */
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(10);
        tree.root.left = new Node(8);
        tree.root.right = new Node(2);
        tree.root.left.left = new Node(3);
        tree.root.right.right = new Node(90);
  
        // Populates nextRight pointer in all nodes 
        tree.connect(tree.root);
  
        // Let us check the values of nextRight pointers 
        int a = tree.root.nextRight != null ? tree.root.nextRight.data : -1;
        int b = tree.root.left.nextRight != null ? tree.root.left.nextRight.data : -1;
        int c = tree.root.right.nextRight != null ? tree.root.right.nextRight.data : -1;
        int d = tree.root.left.left.nextRight != null ? tree.root.left.left.nextRight.data : -1;
        int e = tree.root.right.right.nextRight != null ? tree.root.right.right.nextRight.data : -1;
  
        // Now lets print the values 
        Console.WriteLine("Following are populated nextRight pointers in " + " the tree(-1 is printed if there is no nextRight)");
        Console.WriteLine("nextRight of " + tree.root.data + " is " + a);
        Console.WriteLine("nextRight of " + tree.root.left.data + " is " + b);
        Console.WriteLine("nextRight of " + tree.root.right.data + " is " + c);
        Console.WriteLine("nextRight of " + tree.root.left.left.data + " is " + d);
        Console.WriteLine("nextRight of " + tree.root.right.right.data + " is " + e);
    }
}
  
  // This code is contributed by Shrikant13

Javascript

<script>
      
    // Iterative Javascript program to connect nodes at same level
    // using constant extra space
      
    class Node
    {
        constructor(item) {
              this.data = item;
            this.left = null;
            this.right = null;
            this.nextRight = null;
        }
    }
      
    let root;
    
    /* This function returns the leftmost 
    child of nodes at the same level
    as p. This function is used to getNExt right of p's right child
    If right child of is NULL then this can also be used for the
    left child */
    function getNextRight(p)
    {
        let temp = p.nextRight;
    
        /* Traverse nodes at p's level and find and return
           the first node's first child */
        while (temp != null)
        {
            if (temp.left != null)
                return temp.left;
            if (temp.right != null)
                return temp.right;
            temp = temp.nextRight;
        }
    
        // If all the nodes at p's level are 
        // leaf nodes then return NULL
        return null;
    }
    
    /* Sets nextRight of all nodes of a tree with root as p */
    function connect(p) {
        let temp = null;
    
        if (p == null)
            return;
    
        // Set nextRight for root
        p.nextRight = null;
    
        // set nextRight of all levels one by one
        while (p != null)
        {
            let q = p;
    
            /* Connect all children nodes of p and
               children nodes of all other
               nodes at same level as p */
            while (q != null)
            {
                // Set the nextRight pointer for p's left child
                if (q.left != null)
                {
                    
                    // If q has right child, then 
                    // right child is nextRight of
                    // p and we also need to set 
                    // nextRight of right child
                    if (q.right != null)
                        q.left.nextRight = q.right;
                    else
                        q.left.nextRight = getNextRight(q);
                }
    
                if (q.right != null)
                    q.right.nextRight = getNextRight(q);
    
                // Set nextRight for other nodes 
                // in pre order fashion
                q = q.nextRight;
            }
    
            // start from the first node of next level
            if (p.left != null)
                p = p.left;
            else if (p.right != null)
                p = p.right;
            else
                p = getNextRight(p);
        }
    }
      
    /* Constructed binary tree is
                 10
               /   \
             8      2
           /         \
         3            90
        */
    root = new Node(10);
    root.left = new Node(8);
    root.right = new Node(2);
    root.left.left = new Node(3);
    root.right.right = new Node(90);
  
    // Populates nextRight pointer in all nodes
    connect(root);
  
    // Let us check the values of nextRight pointers
    let a = root.nextRight != null ?
      root.nextRight.data : -1;
    let b = root.left.nextRight != null ?
      root.left.nextRight.data : -1;
    let c = root.right.nextRight != null ?
      root.right.nextRight.data : -1;
    let d = root.left.left.nextRight != null ?
      root.left.left.nextRight.data : -1;
    let e = root.right.right.nextRight != null ?
      root.right.right.nextRight.data : -1;
  
    // Now lets print the values
    document.write("Following are populated nextRight pointers in "
            + " the tree(-1 is printed if there is no nextRight)" + 
                   "</br>");
    document.write("nextRight of " + root.data + " is " + a + 
                                  "</br>");
    document.write("nextRight of " + root.left.data
                       + " is " + b + "</br>");
    document.write("nextRight of " + root.right.data +
                       " is " + c + "</br>");
    document.write("nextRight of " + root.left.left.data +
                       " is " + d + "</br>");
    document.write("nextRight of " + root.right.right.data +
                       " is " + e + "</br>");
    
</script>

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *