连接同一级别的节点（级别顺序遍历）-yiteyi-C++库

编写一个函数，将二叉树中同一级别的所有相邻节点连接起来。

null

例子：

Input Tree       A      /      B   C    /       D   E   FOutput Tree       A--->NULL      /      B-->C-->NULL    /       D-->E-->F-->NULL

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

我们已经讨论了O（n^2）时间和O方法连接同一级别的节点由于morris遍历在最坏的情况下可能是O（n），调用它来设置右指针可能会导致O（n^2）时间复杂度。在本文中，我们讨论了水平顺序遍历使用空标记来标记树中的级别。

C++

                         // Connect nodes at same level using level order                       
                         // traversal.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         struct                                     Node {                       
                                                 int                                     data;                       
                                                 struct                                     Node* left, *right, *nextRight;                       
                         };                       
           
                         // Sets nextRight of all nodes of a tree                       
                         void                                     connect(                                     struct                                     Node* root)                       
                         {                       
                                                 queue<Node*> q;                       
                                                 q.push(root);                       
           
                                                 // null marker to represent end of current level                       
                                                 q.push(NULL);                       
           
                                                 // Do Level order of tree using NULL markers                       
                                                 while                                     (!q.empty()) {                       
                                                 Node *p = q.front();                       
                                                 q.pop();                       
                                                 if                                     (p != NULL) {                       
           
                                                 // next element in queue represents next                       
                                                 // node at current Level                       
                                                 p->nextRight = q.front();                       
           
                                                 // push left and right children of current                       
                                                 // node                       
                                                 if                                     (p->left)                       
                                                 q.push(p->left);                       
                                                 if                                     (p->right)                       
                                                 q.push(p->right);                       
                                                 }                       
                                   
                                                 // if queue is not empty, push NULL to mark                       
                                                 // nodes at this level are visited                       
                                                 else                                     if                                     (!q.empty())                       
                                                 q.push(NULL);                       
                                                 }                       
                         }                       
           
                         /* 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 = node->right = 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) "                                     );                       
                                                 printf                                     (                                     "nextRight of %d is %d "                                     , root->data,                       
                                                 root->nextRight ? root->nextRight->data : -1);                       
                                                 printf                                     (                                     "nextRight of %d is %d "                                     , root->left->data,                       
                                                 root->left->nextRight ? root->left->nextRight->data : -1);                       
                                                 printf                                     (                                     "nextRight of %d is %d "                                     , root->right->data,                       
                                                 root->right->nextRight ? root->right->nextRight->data : -1);                       
                                                 printf                                     (                                     "nextRight of %d is %d "                                     , root->left->left->data,                       
                                                 root->left->left->nextRight ? root->left->left->nextRight->data : -1);                       
                                                 printf                                     (                                     "nextRight of %d is %d "                                     , root->right->right->data,                       
                                                 root->right->right->nextRight ? root->right->right->nextRight->data : -1);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Connect nodes at same level using level order                       
                         // traversal.                       
                         import                                     java.util.LinkedList;                       
                         import                                     java.util.Queue;                       
                         public                                     class                                     Connect_node_same_level {                       
                                   
                                                 // Node class                       
                                                 static                                     class                                     Node {                       
                                                 int                                     data;                       
                                                 Node left, right, nextRight;                       
                                                 Node(                                     int                                     data){                       
                                                 this                                     .data = data;                       
                                                 left =                                     null                                     ;                       
                                                 right =                                     null                                     ;                       
                                                 nextRight =                                     null                                     ;                       
                                                 }                       
                                                 };                       
                                   
                                                 // Sets nextRight of all nodes of a tree                       
                                                 static                                     void                                     connect(Node root)                       
                                                 {                       
                                                 Queue<Node> q =                                     new                                     LinkedList<Node>();                       
                                                 q.add(root);                       
                                   
                                                 // null marker to represent end of current level                       
                                                 q.add(                                     null                                     );                       
                                   
                                                 // Do Level order of tree using NULL markers                       
                                                 while                                     (!q.isEmpty()) {                       
                                                 Node p = q.peek();                       
                                                 q.remove();                       
                                                 if                                     (p !=                                     null                                     ) {                       
                                   
                                                 // next element in queue represents next                       
                                                 // node at current Level                       
                                                 p.nextRight = q.peek();                       
                                   
                                                 // push left and right children of current                       
                                                 // node                       
                                                 if                                     (p.left !=                                     null                                     )                       
                                                 q.add(p.left);                       
                                                 if                                     (p.right !=                                     null                                     )                       
                                                 q.add(p.right);                       
                                                 }                       
                                   
                                                 // if queue is not empty, push NULL to mark                       
                                                 // nodes at this level are visited                       
                                                 else                                     if                                     (!q.isEmpty())                       
                                                 q.add(                                     null                                     );                       
                                                 }                       
                                                 }                       
                                   
                                                 /* Driver program to test above functions*/                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                   
                                                 /* 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                       
                                                 connect(root);                       
                                   
                                                 // Let us check the values of nextRight pointers                       
                                                 System.out.println(                                     "Following are populated nextRight pointers in "                                     +                       
                                                 "the tree (-1 is printed if there is no nextRight)"                                     );                       
                                                 System.out.println(                                     "nextRight of "                                     + root.data +                                     " is "                                     +                       
                                                 ((root.nextRight !=                                     null                                     ) ? root.nextRight.data : -                                     1                                     ));                       
                                                 System.out.println(                                     "nextRight of "                                     + root.left.data+                                     " is "                                     +                       
                                                 ((root.left.nextRight !=                                     null                                     ) ? root.left.nextRight.data : -                                     1                                     ));                       
                                                 System.out.println(                                     "nextRight of "                                     + root.right.data+                                     " is "                                     +                       
                                                 ((root.right.nextRight !=                                     null                                     ) ? root.right.nextRight.data : -                                     1                                     ));                       
                                                 System.out.println(                                     "nextRight of "                                     +  root.left.left.data+                                     " is "                                     +                       
                                                 ((root.left.left.nextRight !=                                     null                                     ) ? root.left.left.nextRight.data : -                                     1                                     ));                       
                                                 System.out.println(                                     "nextRight of "                                     +  root.right.right.data+                                     " is "                                     +                       
                                                 ((root.right.right.nextRight !=                                     null                                     ) ? root.right.right.nextRight.data : -                                     1                                     ));                       
                                                 }                       
                         }                       
                         // This code is contributed by Sumit Ghosh                       

Python3

                         #! /usr/bin/env python3                       
           
                         # connect nodes at same level using level order traversal                       
                         import                                     sys                       
           
           
                         class                                     Node:                       
                                                 def                                     __init__(                                     self                                     , data):                       
                                                 self                                     .data                                     =                                     data                       
                                                 self                                     .left                                     =                                     None                       
                                                 self                                     .right                                     =                                     None                       
                                                 self                                     .nextRight                                     =                                     None                       
           
                                                 def                                     __str__(                                     self                                     ):                       
                                                 return                                     '{}'                                     .                                     format                                     (                                     self                                     .data)                       
           
           
                         def                                     printLevelByLevel(root):                       
                                                 # print level by level                       
                                                 if                                     root:                       
                                                 node                                     =                                     root                       
                                                 while                                     node:                       
                                                 print                                     (                                     '{}'                                     .                                     format                                     (node.data), end                                     =                                     ' '                                     )                       
                                                 node                                     =                                     node.nextRight                       
                                                 print                                     ()                       
                                                 if                                     root.left:                       
                                                 printLevelByLevel(root.left)                       
                                                 else                                     :                       
                                                 printLevelByLevel(root.right)                       
           
           
                         def                                     inorder(root):                       
                                                 if                                     root:                       
                                                 inorder(root.left)                       
                                                 print                                     (root.data, end                                     =                                     ' '                                     )                       
                                                 inorder(root.right)                       
           
           
                         def                                     connect(root):                       
                                                 # set nextRight of all nodes of a tree                       
                                                 queue                                     =                                     []                       
                                                 queue.append(root)                       
                                                 # null marker to represent end of current level                       
                                                 queue.append(                                     None                                     )                       
                                                 # do level order of tree using None markers                       
                                                 while                                     queue:                       
                                                 p                                     =                                     queue.pop(                                     0                                     )                       
                                                 if                                     p:                       
                                                 # next element in queue represents                       
                                                 # next node at current level                       
                                                 p.nextRight                                     =                                     queue[                                     0                                     ]                       
                                                 # pus left and right children of current node                       
                                                 if                                     p.left:                       
                                                 queue.append(p.left)                       
                                                 if                                     p.right:                       
                                                 queue.append(p.right)                       
                                                 elif                                     queue:                       
                                                 queue.append(                                     None                                     )                       
           
           
                         def                                     main():                       
                                                 """Driver program to test above functions.                       
                                                 Constructed binary tree is                       
                                                 10                       
                                                 /                       
                                                 8      2                       
                                                 /                       
                                                 3            90                       
                                                 """                       
           
                                                 root                                     =                                     Node(                                     10                                     )                       
                                                 root.left                                     =                                     Node(                                     8                                     )                       
                                                 root.right                                     =                                     Node(                                     2                                     )                       
                                                 root.left.left                                     =                                     Node(                                     3                                     )                       
                                                 root.right.right                                     =                                     Node(                                     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) "                                     )                       
                                                 if                                     (root.nextRight !                                     =                                     None                                     ):                       
                                                 print                                     (                                     "nextRight of %d is %d "                                     %                                     (root.data,root.nextRight.data))                       
                                                 else                                     :                       
                                                 print                                     (                                     "nextRight of %d is %d "                                     %                                     (root.data,                                     -                                     1                                     ))                       
                                                 if                                     (root.left.nextRight !                                     =                                     None                                     ):                       
                                                 print                                     (                                     "nextRight of %d is %d "                                     %                                     (root.left.data,root.left.nextRight.data))                       
                                                 else                                     :                       
                                                 print                                     (                                     "nextRight of %d is %d "                                     %                                     (root.left.data,                                     -                                     1                                     ))                       
                                                 if                                     (root.right.nextRight !                                     =                                     None                                     ):                       
                                                 print                                     (                                     "nextRight of %d is %d "                                     %                                     (root.right.data,root.right.nextRight.data))                       
                                                 else                                     :                       
                                                 print                                     (                                     "nextRight of %d is %d "                                     %                                     (root.right.data,                                     -                                     1                                     ))                       
                                                 if                                     (root.left.left.nextRight !                                     =                                     None                                     ):                       
                                                 print                                     (                                     "nextRight of %d is %d "                                     %                                     (root.left.left.data,root.left.left.nextRight.data))                       
                                                 else                                     :                       
                                                 print                                     (                                     "nextRight of %d is %d "                                     %                                     (root.left.left.data,                                     -                                     1                                     ))                       
                                                 if                                     (root.right.right.nextRight !                                     =                                     None                                     ):                       
                                                 print                                     (                                     "nextRight of %d is %d "                                     %                                     (root.right.right.data,root.right.right.nextRight.data))                       
                                                 else                                     :                       
                                                 print                                     (                                     "nextRight of %d is %d "                                     %                                     (root.right.right.data,                                     -                                     1                                     ))                       
                                   
                                                 print                                     ()                       
           
           
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
                                                 main()                       
           
                         # This code is contributed by Ram Basnet                       

C#

                         // Connect nodes at same level using level order                       
                         // traversal.                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         public                                     class                                     Connect_node_same_level                       
                         {                       
                                   
                                                 // Node class                       
                                                 class                                     Node                       
                                                 {                       
                                                 public                                     int                                     data;                       
                                                 public                                     Node left, right, nextRight;                       
                                                 public                                     Node(                                     int                                     data)                       
                                                 {                       
                                                 this                                     .data = data;                       
                                                 left =                                     null                                     ;                       
                                                 right =                                     null                                     ;                       
                                                 nextRight =                                     null                                     ;                       
                                                 }                       
                                                 };                       
                                   
                                                 // Sets nextRight of all nodes of a tree                       
                                                 static                                     void                                     connect(Node root)                       
                                                 {                       
                                                 Queue<Node> q =                                     new                                     Queue<Node>();                       
                                                 q.Enqueue(root);                       
                                   
                                                 // null marker to represent end of current level                       
                                                 q.Enqueue(                                     null                                     );                       
                                   
                                                 // Do Level order of tree using NULL markers                       
                                                 while                                     (q.Count!=0)                       
                                                 {                       
                                                 Node p = q.Peek();                       
                                                 q.Dequeue();                       
                                                 if                                     (p !=                                     null                                     )                       
                                                 {                       
                                   
                                                 // next element in queue represents next                       
                                                 // node at current Level                       
                                                 p.nextRight = q.Peek();                       
                                   
                                                 // push left and right children of current                       
                                                 // node                       
                                                 if                                     (p.left !=                                     null                                     )                       
                                                 q.Enqueue(p.left);                       
                                                 if                                     (p.right !=                                     null                                     )                       
                                                 q.Enqueue(p.right);                       
                                                 }                       
                                   
                                                 // if queue is not empty, push NULL to mark                       
                                                 // nodes at this level are visited                       
                                                 else                                     if                                     (q.Count!=0)                       
                                                 q.Enqueue(                                     null                                     );                       
                                                 }                       
                                                 }                       
                                   
                                                 /* Driver code*/                       
                                                 public                                     static                                     void                                     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                       
                                                 connect(root);                       
                                   
                                                 // Let us check the values of nextRight pointers                       
                                                 Console.WriteLine(                                     "Following are populated nextRight pointers in "                                     +                       
                                                 "the tree (-1 is printed if there is no nextRight)"                                     );                       
                                                 Console.WriteLine(                                     "nextRight of "                                     + root.data +                                     " is "                                     +                       
                                                 ((root.nextRight !=                                     null                                     ) ? root.nextRight.data : -1));                       
                                                 Console.WriteLine(                                     "nextRight of "                                     + root.left.data+                                     " is "                                     +                       
                                                 ((root.left.nextRight !=                                     null                                     ) ? root.left.nextRight.data : -1));                       
                                                 Console.WriteLine(                                     "nextRight of "                                     + root.right.data+                                     " is "                                     +                       
                                                 ((root.right.nextRight !=                                     null                                     ) ? root.right.nextRight.data : -1));                       
                                                 Console.WriteLine(                                     "nextRight of "                                     + root.left.left.data+                                     " is "                                     +                       
                                                 ((root.left.left.nextRight !=                                     null                                     ) ? root.left.left.nextRight.data : -1));                       
                                                 Console.WriteLine(                                     "nextRight of "                                     + root.right.right.data+                                     " is "                                     +                       
                                                 ((root.right.right.nextRight !=                                     null                                     ) ? root.right.right.nextRight.data : -1));                       
                                                 }                       
                         }                       
           
                         /* This code is contributed by Rajput-Ji*/                       

Javascript

                         <script>                       
                                                 // Connect nodes at same level using level order traversal.                       
                                   
                                                 // A Binary Tree Node                       
                                                 class Node                       
                                                 {                       
                                                 constructor(data, nextRight) {                       
                                                 this                                     .left =                                     null                                     ;                       
                                                 this                                     .right =                                     null                                     ;                       
                                                 this                                     .data = data;                       
                                                 this                                     .nextRight = nextRight;                       
                                                 }                       
                                                 }                       
                                   
                                                 // Sets nextRight of all nodes of a tree                       
                                                 function                                     connect(root)                       
                                                 {                       
                                                 let q = [];                       
                                                 q.push(root);                       
                                   
                                                 // null marker to represent end of current level                       
                                                 q.push(                                     null                                     );                       
                                   
                                                 // Do Level order of tree using NULL markers                       
                                                 while                                     (q.length > 0) {                       
                                                 let p = q[0];                       
                                                 q.shift();                       
                                                 if                                     (p !=                                     null                                     ) {                       
                                   
                                                 // next element in queue represents next                       
                                                 // node at current Level                       
                                                 p.nextRight = q[0];                       
                                   
                                                 // push left and right children of current                       
                                                 // node                       
                                                 if                                     (p.left !=                                     null                                     )                       
                                                 q.push(p.left);                       
                                                 if                                     (p.right !=                                     null                                     )                       
                                                 q.push(p.right);                       
                                                 }                       
                                   
                                                 // if queue is not empty, push NULL to mark                       
                                                 // nodes at this level are visited                       
                                                 else                                     if                                     (q.length > 0)                       
                                                 q.push(                                     null                                     );                       
                                                 }                       
                                                 }                       
                                   
                                                 /* Constructed binary tree is                       
                                                 10                       
                                                 /                       
                                                 8      2                       
                                                 /                       
                                                 3            90                       
                                                 */                       
                                                 let 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                       
                                                 document.write(                                     "Following are populated nextRight pointers in "                                     +                                     "</br>"                                     +                       
                                                 "the tree (-1 is printed if there is no nextRight)"                                     +                                     "</br>"                                     );                       
                                                 document.write(                                     "nextRight of "                                     + root.data +                                     " is "                                     +                       
                                                 ((root.nextRight !=                                     null                                     ) ? root.nextRight.data : -1) +                                     "</br>"                                     );                       
                                                 document.write(                                     "nextRight of "                                     + root.left.data+                                     " is "                                     +                       
                                                 ((root.left.nextRight !=                                     null                                     ) ? root.left.nextRight.data : -1) +                                     "</br>"                                     );                       
                                                 document.write(                                     "nextRight of "                                     + root.right.data+                                     " is "                                     +                       
                                                 ((root.right.nextRight !=                                     null                                     ) ? root.right.nextRight.data : -1) +                                     "</br>"                                     );                       
                                                 document.write(                                     "nextRight of "                                     +  root.left.left.data+                                     " is "                                     +                       
                                                 ((root.left.left.nextRight !=                                     null                                     ) ? root.left.left.nextRight.data : -1) +                                     "</br>"                                     );                       
                                                 document.write(                                     "nextRight of "                                     +  root.right.right.data+                                     " is "                                     +                       
                                                 ((root.right.right.nextRight !=                                     null                                     ) ? root.right.right.nextRight.data : -1) +                                     "</br>"                                     );                       
           
                         // This code is contributed by divyesh072019.                       
                         </script>                       

输出：

Following are populated nextRight pointers in the tree (-1 is printed if there is no nextRight) nextRight of 10 is -1 nextRight of 8 is 2 nextRight of 2 is -1 nextRight of 3 is 90 nextRight of 90 is -1

时间复杂性： O（n），其中n是节点数

替代实施： 我们还可以遵循中讨论的实现逐行打印水平顺序遍历|集1 .我们通过跟踪以前访问过的同级节点来保持连接同级节点。

实施： https://ide.geeksforgeeks.org/gV1Oc2 感谢Akilan Sengottayan提出的这一替代实施方案。

本文由 阿披实拉吉普特 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章