각 노드에서 다음 오른쪽 포인터 채우기


난이도 중급
자주 묻는 질문 아마존 블룸버그 페이스북 서비스 Microsoft
폭 우선 검색 깊이 우선 검색 나무

주어진 이진 트리, 같은 수준에있는 노드를 왼쪽에서 오른쪽으로 연결합니다.

트리 노드의 구조: 트리의 노드는 트리 노드 유형의 데이터 (정수 값), 포인터 (다음, 왼쪽, 오른쪽)의 4 가지 구성 요소를 포함합니다. 노드의 다음 포인터는 같은 수준에서 오른쪽 노드를 가리 킵니다. 노드가 해당 수준에서 가장 오른쪽 노드이면 다음 포인터가 null 값을 가리 킵니다. 왼쪽 및 오른쪽 포인터는 각각 왼쪽 및 오른쪽 자식을 가리 킵니다. 구조는 나무 노드는 다음과 같습니다.

입력 :

각 노드에서 다음 오른쪽 포인터 채우기

출력 :

각 노드에서 다음 오른쪽 포인터 채우기

입력 :

각 노드에서 다음 오른쪽 포인터 채우기

출력 :

각 노드에서 다음 오른쪽 포인터 채우기

입력 :

각 노드에서 다음 오른쪽 포인터 채우기

출력 :

각 노드에서 다음 오른쪽 포인터 채우기

설명

  1. 두 노드를 연결하려면 ab 왼쪽에서 오른쪽으로 다음 작업을 수행합니다. a-> 다음 = b.
  2. 처음에는 다음 것 모든 트리 노드의 포인터는 없는.
  3. 장치를 설정하는 알고리즘 다음 것 각 노드의 포인터 다음 것 같은 수준의 노드 (오른쪽으로).
  4. 그리고, 다음 것 각 수준에서 가장 오른쪽 노드의 포인터는 없는.

솔루션 유형

  1. 레벨 순서 순회 / BFS (Breadth First Search).
  2. 순회 선주문
  3. 일정한 공간 – 재귀
  4. 일정한 공간 – 반복

레벨 순서 순회 / BFS

각 노드에서 다음 오른쪽 포인터를 채우기위한 접근 방식

아이디어는 수행하는 것입니다 BFS 주어진 이진 트리에서 레벨 순서 방식으로 노드를 저장하는 큐를 사용합니다. 대기열에 노드를 레벨 번호와 함께 저장합니다. 일단 특정 레벨의 모든 노드를 저장했으면 간단히 하나씩 팝하고 이전에 팝된 노드를 현재 팝된 노드와 연결합니다. 다음 것 바늘. 또한, 다음 것 맨 오른쪽 (레벨의 마지막 팝 노드) 노드가 가리켜 야합니다. 없는.

암호알고리즘

  1. 주어진 이진 트리에서 BFS를 수행합니다. 트리에서 BFS를 수행하는 동안 특정 수준의 모든 노드가 대기열로 푸시됩니다.
  2. 큐에서 동일한 수준 (이진 트리)에있는 모든 노드를 하나씩 팝합니다.
  3. 노드를 팝하는 동안 다음 것 현재 노드에 대한 이전 노드의 포인터.
  4. 이진 트리의 모든 수준에 대해 2 단계와 3 단계를 수행합니다.

위의 알고리즘은 다음과 같습니다.

 

각 노드에서 다음 오른쪽 포인터 채우기

각 노드에서 다음 오른쪽 포인터 채우기

실시

C ++ 프로그램
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// blueprint of the tree node
class Node
{
    public : 
    int data;
    Node *left, *right, *next;
    
    Node(int key)
    {
        data = key;
        left = right = next = NULL;
    }
};

// function that makes appropriate connections    
void connect(Node *root) 
{ 
    // create queue to hold nodes at same level  
    queue <Node*> q;
    
    // insert root node
    q.push(root); 
    
    // used to store the current node
    Node* temp = NULL; 
    
    while (!q.empty()) 
    { 
        int n = q.size(); 
        for (int i = 0; i < n; i++) 
        { 
            // previous stores last popped node from the queue
            Node* prev = temp; 
            temp = q.front();
            q.pop();

            /*
            when i = 0, prev is the first node of a level
            so we have to skip this node.
            and change next pointer from next node onwards
            */
            if (i > 0) 
                prev->next = temp;  

            if (temp->left != NULL) 
                q.push(temp->left); 

            if (temp->right != NULL) 
                q.push(temp->right); 
        } 

        // pointing last node of a particular level to null 
        temp->next = NULL;  
    } 
} 

// Function to print node values of a particular level
void printLevel(Node* root)
{
    if(root == NULL)
    {
        cout<<endl;
        return;
    }
    
    cout<<root->data<<" ";
    printLevel(root->next);
}


int main()
{
    /* create the binary tree*/
    Node *root = NULL;
    
    root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(6);
    
    connect(root);
        
    cout<<"1st Level : ";
    printLevel(root);
    
    cout<<"2nd Level : ";
    printLevel(root->left);
    
    cout<<"3rd Level : ";
    printLevel(root->left->left);
    
    return 0;
}
1st Level : 1 
2nd Level : 2 3 
3rd Level : 4 5 6
자바 프로그램
import java.util.*;
import java.io.*;

class tutorialCup
{
    // blueprint of the tree node
    static class Node
    {
        int data;
        Node left, right, next;
        
        Node(int key)
        {
            data = key;
            left = right = next = null;
        }
    }
    
    // function that makes appropriate connections    
    static void connect(Node root) 
    { 
        // create queue to hold nodes at same level  
        Queue<Node> q = new LinkedList<>(); 
        
        // insert root node
        q.add(root); 
        
        // used to store the current node
        Node temp = null; 
        
        while (!q.isEmpty()) 
        { 
            int n = q.size(); 
            for (int i = 0; i < n; i++) 
            { 
                // previous stores last popped node from the queue
                Node prev = temp; 
                temp = q.poll(); 
  
                /*
                when i = 0, prev is the first node of a level
                so we have to skip this node.
                and change next pointer from next node onwards
                */
                if (i > 0) 
                    prev.next = temp;  
  
                if (temp.left != null) 
                    q.add(temp.left); 
  
                if (temp.right != null) 
                    q.add(temp.right); 
            } 
  
            // pointing last node of a particular level to null 
            temp.next = null;  
        } 
    } 
    
    // Function to print node values of a particular level
    static void printLevel(Node root)
    {
        if(root == null)
        {
            System.out.println();
            return;
        }
        
        System.out.print(root.data+" ");
        printLevel(root.next);
    }
    
    // main Function to implement above function
    public static void main (String[] args) 
    {   
        /* create the binary tree*/
        Node root = null;
    
        root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.right = new Node(6);
        
        connect(root);
        
        System.out.print("1st Level : ");
        printLevel(root);
        
        System.out.print("2nd Level : ");
        printLevel(root.left);
        
        System.out.print("3rd Level : ");
        printLevel(root.left.left);
    }

}
1st Level : 1 
2nd Level : 2 3 
3rd Level : 4 5 6

각 노드에서 다음 오른쪽 포인터를 채우기위한 복잡성 분석

  • 시간 복잡도 : T (n) = O (n), 트리의 각 노드가 처리됩니다.
  • 공간 복잡성 : A (n) = O (n).

순회 선주문

각 노드에서 다음 오른쪽 포인터를 채우기위한 접근 방식

이 방법은 완전한 이진 트리.

완전한 이진 트리: A 완전한 이진 트리 하는 이진 트리 마지막 레벨을 제외한 모든 레벨이 완전히 채워지고 모든 노드가 가능한 한 멀리 남아 있습니다. 아래는 완전한 이진 트리의 예입니다.

다음은 지원 완전한 이진 트리.

아이디어는 할당하는 것입니다 다음 것 사전 주문 방식으로 각 노드의 포인터, 즉 다음 것 이전에 할당 된 상위 노드의 다음 것 자식 노드의.

주어진 트리는 완전한 이진 트리이므로 다음과 같은 명령문을 작성할 수 있습니다.

  1. 부모 노드의 경우 년부터, 다음 것 의 왼쪽 자식 년부터 의 올바른 자식이 될 것입니다 평가. 즉, par-> left-> next = par-> right.
  2. 다음 것 의 오른쪽 자식 년부터 남아있을 것입니다 다음 것 of 평가. 즉, par-> right-> next = par-> next-> left.
  3. 트리에서 가장 오른쪽 부모의 오른쪽 자식은 없는. 즉 par-> right-> next = null로 (파가 가장 오른쪽 부모 인 경우).

위의 관찰을 수행 한 후 트리에있는 모든 노드의 다음 포인터를 할당 할 수있는 재귀 사전 주문 (자녀보다 부모 처리) 알고리즘을 설계 할 수 있습니다.

암호알고리즘

  1. 기본 케이스를 정의하십시오.
  2. 양수인 다음 것 부모 노드의 왼쪽 자식에서 par의 오른쪽 자식으로, 즉 par-> left-> next = par-> right.
  3. 양수인 다음 것 부모 노드의 오른쪽 자식에서 왼쪽 자식 par-> next. 즉, par-> right-> next = par-> next-> left.
  4. 부모 노드의 왼쪽 및 오른쪽 자식에 대해 2 단계와 3 단계를 반복적으로 수행합니다.

위의 알고리즘은 다음과 같습니다.

실시

C ++ 프로그램
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// blueprint of the tree node
class Node
{
    public : 
    int data;
    Node *left, *right, *next;
    
    Node(int key)
    {
        data = key;
        left = right = next = NULL;
    }
};

/*a utility function to Set next pointers of all descendents of par node  
and recursively perform the same for left and right child of par (Preorder traversal)*/
void utility(Node* par) 
{ 
    // define base case 
    if (!par) 
        return; 
  
    // set next pointer of par's left child 
    if (par->left) 
        par->left->next = par->right; 
  
    /* set next pointer of par's right child
    as per the method discussed above */
    if (par->right) 
        par->right->next = (par->next) ? par->next->left : NULL; 
  
    /* recursively set next of children nodes 
    in a preorder fashion*/
    utility(par->left); 
    utility(par->right); 
} 

/* function that sets next pointers of 
nodes in the tree using utility function*/ 
void connect(Node *root) 
{ 
    if(!root)
    return;
    
    root->next = NULL;
    utility(root);
} 

// Function to print node values of a particular level
void printLevel(Node* root)
{
    if(root == NULL)
    {
        cout<<endl;
        return;
    }
    
    cout<<root->data<<" ";
    printLevel(root->next);
}


int main()
{
    /* create the binary tree*/
    Node *root = NULL;
    
    /* for above algorithm to work properly 
        we have to construct a complete binary tree */
    root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    root->left->left->left = new Node(8);
    root->left->left->right = new Node(9);
    
    connect(root);
    cout<<"1st Level : ";
    printLevel(root);
    
    cout<<"2nd Level : ";
    printLevel(root->left);
    
    cout<<"3rd Level : ";
    printLevel(root->left->left);
    
    cout<<"4th Level : ";
    printLevel(root->left->left->left);
    
    return 0;
}
1st Level : 1 
2nd Level : 2 3 
3rd Level : 4 5 6 7 
4th Level : 8 9
자바 프로그램
import java.util.*;
import java.io.*;

class tutorialCup
{
    // blueprint of the tree node
    static class Node
    {
        int data;
        Node left, right, next;
        
        Node(int key)
        {
            data = key;
            left = right = next = null;
        }
    }
    
    /*a utility function to Set next pointers of all descendents of par node  
    and recursively perform the same for left and right child of par (Preorder traversal)*/
    static void utility(Node par) 
    { 
        // define base case 
        if (par == null) 
            return; 
      
        // set next pointer of par's left child 
        if (par.left != null) 
            par.left.next = par.right; 
      
        /* set next pointer of par's right child
        as per the method discussed above */
        if (par.right != null) 
            par.right.next = (par.next != null)? par.next.left : null; 
      
        /* recursively set next of children nodes 
        in a preorder fashion*/
        utility(par.left); 
        utility(par.right); 
    } 
    
    /* function that sets next pointers of 
    nodes in the tree using utility function*/ 
    static void connect(Node root) 
    { 
        if(root == null)
        return;
        
        root.next = null;
        utility(root);
    } 
    
    // Function to print node values of a particular level
    static void printLevel(Node root)
    {
        if(root == null)
        {
            System.out.println();
            return;
        }
        
        System.out.print(root.data+" ");
        printLevel(root.next);
    }
    
    // main Function to implement above function
    public static void main (String[] args) 
    {   
        /* create the binary tree*/
        Node root = null;
        
        /* for above algorithm to work properly we have to construct a complete binary tree */
        root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.left.left.left = new Node(8);
        root.left.left.right = new Node(9);
        
        
        connect(root);
        
        System.out.print("1st Level : ");
        printLevel(root);
        
        System.out.print("2nd Level : ");
        printLevel(root.left);
        
        System.out.print("3rd Level : ");
        printLevel(root.left.left);
        
        System.out.print("4th Level : ");
        printLevel(root.left.left.left);
    }
}
1st Level : 1 
2nd Level : 2 3 
3rd Level : 4 5 6 7 
4th Level : 8 9

각 노드에서 다음 오른쪽 포인터를 채우기위한 복잡성 분석

  1. 시간 복잡도 : T (n) = O (n)
  2. 공간 복잡성 : A (n) = O (1)

재귀

각 노드에서 다음 오른쪽 포인터를 채우기위한 접근 방식

이 접근 방식은 이전 접근 방식과 유사하지만 코드를 약간 수정하면 모든 종류의 이진 트리 (완전 여부에 관계없이)에서 작동하도록 만들 수 있습니다.

아이디어는 기본적으로 수준 i의 모든 노드가 (i + 1) 수준의 노드 이전에 다음 포인터를 설정하도록하는 것입니다. 순서대로 (자녀보다 먼저 부모) 순회를 수행하지만 약간의 수정을 통해이를 달성 할 수 있습니다.

다음 순서로 노드를 탐색합니다 : (부모, 부모의 다음 오른쪽, 왼쪽 자식, 오른쪽 자식).

이런 식으로 i 번째 수준의 모든 노드는 (i + 1) 번째 수준의 노드보다 먼저 설정됩니다.

이제 아래 단계에 따라 목표를 달성 할 수 있습니다.

  1. 부모 노드의 왼쪽 자식의 다음 포인터를 설정하면 부모의 오른쪽 자식이 있는지 여부를 확인합니다.
  2. 올바른 자녀가 있으면 간단히 다음 것 왼쪽 아이의 오른쪽. 즉, par-> left-> next = par-> right.
  3. 그렇지 않으면 기본적으로 왼쪽 자식 바로 오른쪽에있는 첫 번째 노드의 주소를 반환하고 간단히 할당하는 함수 nextRight ()를 사용합니다. 다음 것 반환 된 노드에 왼쪽의. 즉, par-> left-> next = nextRight (par).
  4. nextRight ()는 부모 노드를 사용합니다. (평가) 그리고 그것은 다음 것 포인터 (par-> next), 동일한 수준에서 오른쪽으로 향하는 첫 번째 비 리프 (및 자식의 반환 주소 – 왼쪽 / 오른쪽, 어느 쪽이든) 노드를 찾습니다.
  5. 부모 노드의 오른쪽 자식에 대해 nextRight () 함수를 사용하여 같은 수준에서 오른쪽 자식의 오른쪽에있는 노드의 주소를 반환하고 다음 것 반환 된 주소에 대한 포인터. 즉, par-> right-> next = nextRight ().
  6. 같은 수준의 현재 노드 오른쪽에있는 노드가 없으면 간단히 반환합니다. 없는.

암호알고리즘

  1. 현재 노드를 부모 노드로 간주하고 다음 것 현재 레벨의 포인터가 이미 설정되었습니다.
  2. 부모 노드 (존재하는 경우)의 왼쪽 자식 고려 :
    1. 올바른 자식이있는 경우 할당 다음 것 부모의 왼쪽 자식에서 오른쪽 자식으로. 즉, par-> left-> next = par-> right.
    2. 그렇지 않으면 같은 수준에서 다음 노드를 찾아서 할당합니다. 다음 것 왼쪽 자식의, 즉 par-> left = nextRight (par).
    3. 다음에 대해 위의 두 단계를 반복적으로 수행합니다. 다음 것 왼쪽 자식의. (즉, par-> left-> next).
    4. 이러한 방식으로 동일한 수준의 모든 노드가 설정되었습니다.
  3. 왼쪽이 존재하지 않으면 부모 노드의 오른쪽 자식을 고려하십시오.
    1. 같은 수준에서 다음 노드를 찾아 할당 다음 것 오른쪽 자식, 즉 par-> right = nextRight (par).
    2. 2.1 단계와 2.2 단계를 재귀 적으로 수행합니다. 다음 것 오른쪽 자식의. (즉, par-> right-> next).
    3. 이러한 방식으로 동일한 수준의 모든 노드가 설정되었습니다.
  4. 두 아이가 모두 존재하지 않으면 다음 것 부모 노드 (즉, par-> next).

위의 알고리즘은 다음과 같습니다.

실시

C ++ 프로그램
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// blueprint of the tree node
class Node
{
    public : 
    int data;
    Node *left, *right, *next;
    
    Node(int key)
    {
        data = key;
        left = right = next = NULL;
    }
};

/* This function is used to get first pointer just to the right of children of par */
Node* nextRight(Node *par) 
{ 
    // start traversing nodes on the same level with par towards the right
    Node* temp = par->next; 
    
    // move to right until a node with atleast one children is found  
    while(temp != NULL) 
    { 
        // return the first children of node to the right
        if(temp->left != NULL) 
            return temp->left; 
        if(temp->right != NULL) 
            return temp->right; 
        
        // if node to the right has no children. Then,
        // move to next node to the right on same level
        temp = temp->next; 
    } 
  
    // If all the nodes at par level are leaf nodes then return null 
    return NULL; 
} 

// function to recursively set next of all children of parent node par
// It ensures that nodes at ith level are set before those at (i+1)th level
void utility(Node* par) 
{ 
    // base case 
    if (!par) 
       return; 
  
    /* before setting next pointers of children,
    set next pointers of par and the nodes at the same level as par
    */
    if (par->next != NULL) 
       utility(par->next); 
  
    /* Set the next pointer for par's left child */
    if (par->left) 
    { 
       if (par->right) 
       { 
           par->left->next = par->right; 
           par->right->next = nextRight(par); 
       } 
       else
           par->left->next = nextRight(par); 
  
       /* recursively call for next level nodes,
       the call for left child would automatically call 
       all it's right child */
       utility(par->left); 
    } 
  
    /* If left child is null then first node of next level is the right child */
    else if (par->right) 
    { 
        par->right->next = nextRight(par); 
        utility(par->right); 
    } 
    /* if both the children of parent node are null,
    then we move on to next node in the same level*/
    else
       utility(nextRight(par)); 
} 
/* function that sets next pointers of 
nodes in the tree using utility function*/ 
void connect(Node *root) 
{ 
    if(!root)
    return;
    
    root->next = NULL;
    utility(root);
} 

// Function to print node values of a particular level
void printLevel(Node* root)
{
    if(!root)
    {
        cout<<endl;
        return;
    }
    
    cout<<root->data<<" ";
    printLevel(root->next);
}


int main()
{
    
    /* construct the binary tree */
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    
    root->left->left = new Node(4);
    root->right->left = new Node(5);
    root->right->right = new Node(6);
    
    root->left->left->left = new Node(7);
    root->left->left->right = new Node(8);
    root->right->right->right = new Node(9);
    
    connect(root);
    
    cout<<"1st Level : ";
    printLevel(root);
    
    
    cout<<"2nd Level : ";
    printLevel(root->left);
    
    cout<<"3rd Level : ";
    printLevel(root->left->left);
    
    cout<<"4th Level : ";
    printLevel(root->left->left->left);

    return 0;
}
1st Level : 1 
2nd Level : 2 3 
3rd Level : 4 5 6 
4th Level : 7 8 9
자바 프로그램
import java.util.*;
import java.io.*;

class tutorialCup
{
    // blueprint of the tree node
    static class Node
    {
        int data;
        Node left, right, next;
        
        Node(int key)
        {
            data = key;
            left = right = next = null;
        }
    }
    
    /* This function is used to get first pointer just to the right of children of par */
    static Node nextRight(Node par) 
    { 
        // start traversing nodes on the same level with par towards the right
        Node temp = par.next; 
        
        // move to right until a node with atleast one children is found  
        while(temp != null) 
        { 
            // return the first children of node to the right
            if(temp.left != null) 
                return temp.left; 
            if(temp.right != null) 
                return temp.right; 
            
            // if node to the right has no children. Then,
            // move to next node to the right on same level
            temp = temp.next; 
        } 
      
        // If all the nodes at par level are leaf nodes then return null 
        return null; 
    } 
    
    // function to recursively set next of all children of parent node par
    // It ensures that nodes at ith level are set before those at (i+1)th level
    static void utility(Node par) 
    { 
        // base case 
        if (par == null) 
           return; 
      
        /* 
        before setting next pointers of children,
        set next pointers of par and the nodes at the same level as par
        */
        if (par.next != null) 
           utility(par.next); 
      
        /* Set the next pointer for par's left child */
        if (par.left != null) 
        { 
           if (par.right != null) 
           { 
               par.left.next = par.right; 
               par.right.next = nextRight(par); 
           } 
           else
               par.left.next = nextRight(par); 
      
           /* recursively call for next level nodes,
           the call for left child would automatically call 
           all it's right child */
           utility(par.left); 
        } 
      
        /* If left child is null then first node of next level is the right child */
        else if (par.right != null) 
        { 
            par.right.next = nextRight(par); 
            utility(par.right); 
        } 
        /* if both the children of parent node are null,
        then we move on to next node in the same level*/
        else
           utility(nextRight(par)); 
    } 
    
    /* function that sets next pointers of 
    nodes in the tree using utility function*/ 
    static void connect(Node root) 
    { 
        if(root == null)
        return;
        
        root.next = null;
        utility(root);
    } 
    
    // Function to print node values of a particular level
    static void printLevel(Node root)
    {
        if(root == null)
        {
            System.out.println();
            return;
        }
        
        System.out.print(root.data+" ");
        printLevel(root.next);
    }
    
    // main Function to implement above function
    public static void main (String[] args) 
    {   
        /* construct the binary tree */
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        
        root.left.left = new Node(4);
        root.right.left = new Node(5);
        root.right.right = new Node(6);
        
        root.left.left.left = new Node(7);
        root.left.left.right = new Node(8);
        root.right.right.right = new Node(9);
        
        
        connect(root);
        
        System.out.print("1st Level : ");
        printLevel(root);
        
        System.out.print("2nd Level : ");
        printLevel(root.left);
        
        System.out.print("3rd Level : ");
        printLevel(root.left.left);
        
        System.out.print("4th Level : ");
        printLevel(root.left.left.left);
    }
}
1st Level : 1 
2nd Level : 2 3 
3rd Level : 4 5 6 
4th Level : 7 8 9

각 노드에서 다음 오른쪽 포인터를 채우기위한 복잡성 분석

  • 시간 복잡도 : T (n) = O (n)
  • 공간 복잡성 : A (n) = O (1)

반복적 인

각 노드에서 다음 오른쪽 포인터를 채우기위한 접근 방식

아이디어는 위의 재귀 코드를 반복 코드로 변환하는 것입니다. 코드는 두 개의 중첩 된 while 루프로 구성됩니다. 외부 루프는 트리 수준 (또는 세대)을 통해 아래로 이동하는 데 사용되며 내부 루프는 특정 수준의 모든 노드를 통과하는 데 사용됩니다. 특정 수준의 모든 노드를 처리했으면 다음 수준으로 이동합니다.

아이디어는 기본적으로 수준 i의 모든 노드가 (i + 1) 수준의 노드 이전에 다음 포인터를 설정하도록하는 것입니다. 순서대로 (자녀보다 먼저 부모) 순회를 수행하지만 약간의 수정을 통해이를 달성 할 수 있습니다.

다음 순서로 노드를 탐색합니다 : (부모, 부모의 다음 오른쪽, 왼쪽 자식, 오른쪽 자식).

이런 식으로 i 번째 수준의 모든 노드는 (i + 1) 번째 수준의 노드보다 먼저 설정됩니다.

이제 아래 단계에 따라 목표를 달성 할 수 있습니다.

  1. 부모 노드의 왼쪽 자식의 다음 포인터를 설정하면 부모의 오른쪽 자식이 있는지 확인합니다.
  2. 올바른 자녀가 있으면 간단히 다음 것 왼쪽 아이의 오른쪽. 즉, par-> left-> next = par-> right.
  3. 그렇지 않으면 기본적으로 왼쪽 자식 바로 오른쪽에있는 첫 번째 노드의 주소를 반환하고 간단히 할당하는 함수 nextRight ()를 사용합니다. 다음 것 반환 된 노드에 왼쪽의. 즉, par-> left-> next = nextRight (par).
  4. nextRight ()는 부모 노드를 사용합니다. (평가) 그리고 그것은 다음 것 포인터 (par-> next), 동일한 수준에서 오른쪽으로 향하는 첫 번째 비 리프 (및 자식의 반환 주소 – 왼쪽 / 오른쪽, 어느 쪽이든) 노드를 찾습니다.
  5. 부모 노드의 오른쪽 자식에 대해 nextRight () 함수를 사용하여 같은 수준에서 오른쪽 자식의 오른쪽에있는 노드의 주소를 반환하고 다음 것 반환 된 주소에 대한 포인터. 즉, par-> right-> next = nextRight ().
  6. 같은 수준의 현재 노드 오른쪽에있는 노드가 없으면 간단히 반환합니다. 없는.

암호알고리즘

  1. 현재 노드를 부모 노드로 간주하고 다음 것 현재 레벨의 포인터가 이미 설정되었습니다.
  2. 부모 노드 (존재하는 경우)의 왼쪽 자식 고려 :
    1. 올바른 자식이있는 경우 할당 다음 것 부모의 왼쪽 자식에서 오른쪽 자식으로. 즉, par-> left-> next = par-> right.
    2. 그렇지 않으면 같은 수준에서 다음 노드를 찾아서 할당합니다. 다음 것 왼쪽 자식의, 즉 par-> left = nextRight (par).
    3. 위의 두 단계를 반복적으로 수행하십시오. 다음 것 왼쪽 자식의. (즉, par-> left-> next).
    4. 이러한 방식으로 동일한 수준의 모든 노드가 설정되었습니다.
  3. 왼쪽이 존재하지 않으면 부모 노드의 오른쪽 자식을 고려하십시오.
    1. 같은 수준에서 다음 노드를 찾아 할당 다음 것 오른쪽 자식, 즉 par-> right = nextRight (par).
    2. 2.1 단계와 2.2 단계를 반복적으로 수행합니다. 다음 것 오른쪽 자식의. (즉, par-> right-> next).
    3. 이러한 방식으로 동일한 수준의 모든 노드가 설정되었습니다.
  4. 두 자식이 모두 존재하지 않으면 다음을 반복합니다. 다음 것 부모 노드 (즉, par-> next).

위의 알고리즘은 다음과 같습니다.

실시

C ++ 프로그램
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// blueprint of the tree node
class Node
{
    public : 
    int data;
    Node *left, *right, *next;
    
    Node(int key)
    {
        data = key;
        left = right = next = NULL;
    }
};

/* This function is used to get first pointer just to the right of children of par */
Node* nextRight(Node *par) 
{ 
    // start traversing nodes on the same level with par towards the right
    Node* temp = par->next; 
    
    // move to right until a node with atleast one children is found  
    while(temp != NULL) 
    { 
        // return the first children of node to the right
        if(temp->left != NULL) 
            return temp->left; 
        if(temp->right != NULL) 
            return temp->right; 
        
        // if node to the right has no children. Then,
        // move to next node to the right on same level
        temp = temp->next; 
    } 
  
    // If all the nodes at par level are leaf nodes then return null 
    return NULL; 
} 

// function to Iteratively set next of all children of parent node par
// It ensures that nodes at ith level are set before those at (i+1)th level
void connect(Node *root) 
{ 
    
    if (!root)  
    return;  
  
    // set next for root  
    root->next = NULL;  
  
    // set next of all nodes in the current level
    // after which Iterate to next level
    while (root != NULL)  
    {  
        Node* par = root;  
  
        /* Connect all childrem nodes of par and 
        children nodes of all other nodes at 
        same level as par */
        while (par != NULL)  
        {  
            // set the next pointer for par's left child  
            if (par->left)  
            {  
                if (par->right)  
                    par->left->next = par->right;  
                else
                    par->left->next = nextRight(par);  
            }  
            // set next for par's right children
            if (par->right)  
                par->right->next = nextRight(par);  
  
            // set next of all the nodes on the same level as children of par
            par = par->next;  
        }  
  
        // After processing all the nodes of current Level
        // move down to next level
        if (root->left)  
            root = root->left;  
        else if (root->right)  
            root = root->right;  
        else
            root = nextRight(root);  
    }  
} 

// Function to print node values of a particular level
void printLevel(Node* root)
{
    if(!root)
    {
        cout<<endl;
        return;
    }
    
    cout<<root->data<<" ";
    printLevel(root->next);
}


int main()
{
    
    /* construct the binary tree */
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    
    root->left->left = new Node(4);
    root->right->left = new Node(5);
    root->right->right = new Node(6);
    
    root->left->left->left = new Node(7);
    root->left->left->right = new Node(8);
    root->right->right->right = new Node(9);
    
    connect(root);
    
    cout<<"1st Level : ";
    printLevel(root);
    
    
    cout<<"2nd Level : ";
    printLevel(root->left);
    
    cout<<"3rd Level : ";
    printLevel(root->left->left);
    
    cout<<"4th Level : ";
    printLevel(root->left->left->left);

    return 0;
}
1st Level : 1 
2nd Level : 2 3 
3rd Level : 4 5 6 
4th Level : 7 8 9
자바 프로그램
import java.util.*;
import java.io.*;

class tutorialCup
{
    // blueprint of the tree node
    static class Node
    {
        int data;
        Node left, right, next;
        
        Node(int key)
        {
            data = key;
            left = right = next = null;
        }
    }
    
    /* This function is used to get first pointer just to the right of children of par */
    static Node nextRight(Node par) 
    { 
        // start traversing nodes on the same level with par towards the right
        Node temp = par.next; 
        
        // move to right until a node with atleast one children is found  
        while(temp != null) 
        { 
            // return the first children of node to the right
            if(temp.left != null) 
                return temp.left; 
            if(temp.right != null) 
                return temp.right; 
            
            // if node to the right has no children. Then,
            // move to next node to the right on same level
            temp = temp.next; 
        } 
      
        // If all the nodes at par level are leaf nodes then return null 
        return null; 
    } 
    
    // function to Iteratively set next of all children of parent node par
    // It ensures that nodes at ith level are set before those at (i+1)th level
    static void connect(Node root) 
    { 
        
        if (root == null)  
        return;  
      
        // set next for root  
        root.next = null;  
      
        // set next of all nodes in the current level
        // after which Iterate to next level
        while (root != null)  
        {  
            Node par = root;  
      
            /* Connect all children nodes of par and 
            children nodes of all other nodes at 
            same level as par */
            while (par != null)  
            {  
                // set the next pointer for par's left child  
                if (par.left != null)  
                {  
                    if (par.right != null)  
                        par.left.next = par.right;  
                    else
                        par.left.next = nextRight(par);  
                }  
                // set next for par's right children
                if (par.right != null)  
                    par.right.next = nextRight(par);  
      
                // set next of all the nodes on the same level as children of par
                par = par.next;  
            }  
      
            // After processing all the nodes of current Level
            // move down to next level
            if (root.left != null)  
                root = root.left;  
            else if (root.right != null)  
                root = root.right;  
            else
                root = nextRight(root);  
        }  
    } 
    
    // Function to print node values of a particular level
    static void printLevel(Node root)
    {
        if(root == null)
        {
            System.out.println();
            return;
        }
        
        System.out.print(root.data+" ");
        printLevel(root.next);
    }
    
    // main Function to implement above function
    public static void main (String[] args) 
    {   
        /* construct the binary tree */
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        
        root.left.left = new Node(4);
        root.right.left = new Node(5);
        root.right.right = new Node(6);
        
        root.left.left.left = new Node(7);
        root.left.left.right = new Node(8);
        root.right.right.right = new Node(9);
        
        
        connect(root);
        
        System.out.print("1st Level : ");
        printLevel(root);
        
        System.out.print("2nd Level : ");
        printLevel(root.left);
        
        System.out.print("3rd Level : ");
        printLevel(root.left.left);
        
        System.out.print("4th Level : ");
        printLevel(root.left.left.left);
    }
}
1st Level : 1 
2nd Level : 2 3 
3rd Level : 4 5 6 
4th Level : 7 8 9

각 노드에서 다음 오른쪽 포인터를 채우기위한 복잡성 분석

  • 시간 복잡도 : T (n) = O (n)
  • 공간 복잡성 : A (n) = O (1)

참조