在每個節點中填充下一個右指針


難度級別
經常問 亞馬遜 彭博社 Facebook Microsoft微軟
廣度優先搜索 深度優先搜索

給定一個 二叉樹,從左到右連接處於同一級別的節點。

樹節點的結構:樹的節點包含4個組成部分,分別是樹節點類型的數據(整數值)和指針(下一個,左,右)。 節點的下一個指針指向同一級別的右節點。 如果該節點是該級別中最右邊的節點,則它的下一個指針指向空值。 左,右指針分別指向左和右子級。 一個的結構 節點如下圖所示:

輸入:

在每個節點中填充下一個右指針

輸出:

在每個節點中填充下一個右指針

輸入:

在每個節點中填充下一個右指針

輸出:

在每個節點中填充下一個右指針

輸入:

在每個節點中填充下一個右指針

輸出:

在每個節點中填充下一個右指針

解釋

  1. 連接兩個節點 ab 從左到右,您進行以下操作: 下一個 = b.
  2. 最初, 所有樹節點的指針都設置為 空值。
  3. 設定可設定 每個節點的指針 節點(向右)處於同一級別。
  4. 每個級別上最右邊節點的指針設置為 空值。

解決方案類型

  1. 級別順序遍歷/寬度優先搜索(BFS)。
  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
Java程序
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 = (如果par是最右邊的父母)。

完成上述觀察後,我們可以設計一種遞歸預排序算法(先處理父級,再處理子級),該算法能夠分配樹中所有節點的下一個指針。

算法

  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
Java程序
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. 遞歸地執行以上2個步驟 左孩子的身分。(即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
Java程序
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. 反复執行上述2個步驟 左孩子的身分。(即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
Java程序
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)

參考