给定一个二叉树，其中每个节点都具有以下结构，编写一个函数来填充所有节点的下一个指针。每个节点的下一个指针都应该设置为指向有序的后续节点。
null
C++
class node { public : int data; node *left; node *right; node *next; }; // This code is contributed // by Shubham Singh |
C
struct node { int data; struct node* left; struct node* right; struct node* next; } |
JAVA
// A binary tree node class Node { int data; Node left, right, next; Node( int item) { data = item; left = right = next = null ; } } // This code is contributed by SUBHAMSINGH10. |
Python3
class Node: def __init__( self , data): self .data = data self .left = None self .right = None self . next = None # This code is contributed by Shubham Singh |
C#
class Node { public int data; public Node left, right, next; public Node( int item) { data = item; left = right = next = null ; } } Node root; // This code is contributed // by Shubham Singh |
Javascript
<script> class Node { constructor(x) { this .data = x; this .left = null ; this .right = null ; } } // This code is contributed by Shubham Singh </script> |
最初，所有下一个指针都有空值。您的函数应该填充这些下一个指针，以便它们指向有序的后续指针。
解决方案（使用反向顺序遍历） 以相反的顺序遍历给定的树，并跟踪以前访问的节点。在访问节点时，将以前访问过的节点指定为下一个节点。
C++
// C++ program to populate inorder // traversal of all nodes #include<bits/stdc++.h> using namespace std; class node { public : int data; node *left; node *right; node *next; }; /* Set next of p and all descendants of p by traversing them in reverse Inorder */ void populateNext(node* p) { // The first visited node will be the // rightmost node next of the rightmost // node will be NULL static node *next = NULL; if (p) { // First set the next pointer // in right subtree populateNext(p->right); // Set the next as previously visited // node in reverse Inorder p->next = next; // Change the prev for subsequent node next = p; // Finally, set the next pointer in // left subtree populateNext(p->left); } } /* UTILITY FUNCTIONS */ /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ node* newnode( int data) { node* Node = new node(); Node->data = data; Node->left = NULL; Node->right = NULL; Node->next = NULL; return (Node); } // Driver Code int main() { /* Constructed binary tree is 10 / 8 12 / 3 */ node *root = newnode(10); root->left = newnode(8); root->right = newnode(12); root->left->left = newnode(3); // Populates nextRight pointer in all nodes populateNext(root); // Let us see the populated values node *ptr = root->left->left; while (ptr) { // -1 is printed if there is no successor cout << "Next of " << ptr->data << " is " << (ptr->next? ptr->next->data: -1) << endl; ptr = ptr->next; } return 0; } // This code is contributed by rathbhupendra |
JAVA
// Java program to populate inorder traversal of all nodes // A binary tree node class Node { int data; Node left, right, next; Node( int item) { data = item; left = right = next = null ; } } class BinaryTree { Node root; static Node next = null ; /* Set next of p and all descendants of p by traversing them in reverse Inorder */ void populateNext(Node node) { // The first visited node will be the rightmost node // next of the rightmost node will be NULL if (node != null ) { // First set the next pointer in right subtree populateNext(node.right); // Set the next as previously visited node in reverse Inorder node.next = next; // Change the prev for subsequent node next = node; // Finally, set the next pointer in left subtree populateNext(node.left); } } /* Driver program to test above functions*/ public static void main(String args[]) { /* Constructed binary tree is 10 / 8 12 / 3 */ BinaryTree tree = new BinaryTree(); tree.root = new Node( 10 ); tree.root.left = new Node( 8 ); tree.root.right = new Node( 12 ); tree.root.left.left = new Node( 3 ); // Populates nextRight pointer in all nodes tree.populateNext(tree.root); // Let us see the populated values Node ptr = tree.root.left.left; while (ptr != null ) { // -1 is printed if there is no successor int print = ptr.next != null ? ptr.next.data : - 1 ; System.out.println( "Next of " + ptr.data + " is: " + print); ptr = ptr.next; } } } // This code has been contributed by Mayank Jaiswal |
Python3
# Python3 program to populate # inorder traversal of all nodes # Tree node class Node: def __init__( self , data): self .data = data self .left = None self .right = None self . next = None # The first visited node will be # the rightmost node next of the # rightmost node will be None next = None # Set next of p and all descendants of p # by traversing them in reverse Inorder def populateNext(p): global next if (p ! = None ): # First set the next pointer # in right subtree populateNext(p.right) # Set the next as previously visited node # in reverse Inorder p. next = next # Change the prev for subsequent node next = p # Finally, set the next pointer # in left subtree populateNext(p.left) # UTILITY FUNCTIONS # Helper function that allocates # a new node with the given data # and None left and right pointers. def newnode(data): node = Node( 0 ) node.data = data node.left = None node.right = None node. next = None return (node) # Driver Code # Constructed binary tree is # 10 # / # 8 12 # / # 3 root = newnode( 10 ) root.left = newnode( 8 ) root.right = newnode( 12 ) root.left.left = newnode( 3 ) # Populates nextRight pointer # in all nodes p = populateNext(root) # Let us see the populated values ptr = root.left.left while (ptr ! = None ): out = 0 if (ptr. next ! = None ): out = ptr. next .data else : out = - 1 # -1 is printed if there is no successor print ( "Next of" , ptr.data, "is" , out) ptr = ptr. next # This code is contributed by Arnab Kundu |
C#
// C# program to populate inorder traversal of all nodes using System; class BinaryTree { // A binary tree node class Node { public int data; public Node left, right, next; public Node( int item) { data = item; left = right = next = null ; } } Node root; static Node next = null ; /* Set next of p and all descendants of p by traversing them in reverse Inorder */ void populateNext(Node node) { // The first visited node will be the rightmost node // next of the rightmost node will be NULL if (node != null ) { // First set the next pointer in right subtree populateNext(node.right); // Set the next as previously visited node in reverse Inorder node.next = next; // Change the prev for subsequent node next = node; // Finally, set the next pointer in left subtree populateNext(node.left); } } /* Driver program to test above functions*/ static public void Main(String []args ) { /* Constructed binary tree is 10 / 8 12 / 3 */ BinaryTree tree = new BinaryTree(); tree.root = new Node(10); tree.root.left = new Node(8); tree.root.right = new Node(12); tree.root.left.left = new Node(3); // Populates nextRight pointer in all nodes tree.populateNext(tree.root); // Let us see the populated values Node ptr = tree.root.left.left; while (ptr != null ) { // -1 is printed if there is no successor int print = ptr.next != null ? ptr.next.data : -1; Console.WriteLine( "Next of " + ptr.data + " is: " + print); ptr = ptr.next; } } } // This code has been contributed by Arnab Kundu |
Javascript
<script> // Javascript program to populate inorder traversal of all nodes // A binary tree node class Node { constructor(x) { this .data = x; this .left = null ; this .right = null ; } } let root; let next = null ; /* Set next of p and all descendants of p by traversing them in reverse Inorder */ function populateNext(node) { // The first visited node will be the rightmost node // next of the rightmost node will be NULL if (node != null ) { // First set the next pointer in right subtree populateNext(node.right); // Set the next as previously visited node in reverse Inorder node.next = next; // Change the prev for subsequent node next = node; // Finally, set the next pointer in left subtree populateNext(node.left); } } /* Driver program to test above functions*/ /* Constructed binary tree is 10 / 8 12 / 3 */ root = new Node(10) root.left = new Node(8) root.right = new Node(12) root.left.left = new Node(3) // Populates nextRight pointer // in all nodes p = populateNext(root) // Let us see the populated values ptr = root.left.left while (ptr != null ) { // -1 is printed if there is no successor let print = ptr.next != null ? ptr.next.data : -1; document.write( "Next of " + ptr.data + " is: " + print+ "<br>" ); ptr = ptr.next; } // This code is contributed by unknown2108 </script> |
输出：
Next of 3 is 8Next of 8 is 10Next of 10 is 12Next of 12 is -1
通过将对next的引用作为参数传递，我们可以避免使用静态变量。
C++
// An implementation that doesn't use static variable // A wrapper over populateNextRecur void populateNext(node *root) { // The first visited node will be the rightmost node // next of the rightmost node will be NULL node *next = NULL; populateNextRecur(root, &next); } /* Set next of all descendants of p by traversing them in reverse Inorder */ void populateNextRecur(node* p, node **next_ref) { if (p) { // First set the next pointer in right subtree populateNextRecur(p->right, next_ref); // Set the next as previously visited // node in reverse Inorder p->next = *next_ref; // Change the prev for subsequent node *next_ref = p; // Finally, set the next pointer in right subtree populateNextRecur(p->left, next_ref); } } // This is code is contributed by rathbhupendra |
C
// An implementation that doesn't use static variable // A wrapper over populateNextRecur void populateNext( struct node *root) { // The first visited node will be the rightmost node // next of the rightmost node will be NULL struct node *next = NULL; populateNextRecur(root, &next); } /* Set next of all descendants of p by traversing them in reverse Inorder */ void populateNextRecur( struct node* p, struct node **next_ref) { if (p) { // First set the next pointer in right subtree populateNextRecur(p->right, next_ref); // Set the next as previously visited node in reverse Inorder p->next = *next_ref; // Change the prev for subsequent node *next_ref = p; // Finally, set the next pointer in right subtree populateNextRecur(p->left, next_ref); } } |
JAVA
// A wrapper over populateNextRecur void populateNext(Node node) { // The first visited node will be the rightmost node // next of the rightmost node will be NULL populateNextRecur(node, next); } /* Set next of all descendants of p by traversing them in reverse Inorder */ void populateNextRecur(Node p, Node next_ref) { if (p != null ) { // First set the next pointer in right subtree populateNextRecur(p.right, next_ref); // Set the next as previously visited node in reverse Inorder p.next = next_ref; // Change the prev for subsequent node next_ref = p; // Finally, set the next pointer in right subtree populateNextRecur(p.left, next_ref); } } |
Python3
# A wrapper over populateNextRecur def populateNext(node): # The first visited node will be the rightmost node # next of the rightmost node will be NULL populateNextRecur(node, next ) # /* Set next of all descendants of p by # traversing them in reverse Inorder */ def populateNextRecur(p, next_ref): if (p ! = None ): # First set the next pointer in right subtree populateNextRecur(p.right, next_ref) # Set the next as previously visited node in reverse Inorder p. next = next_ref # Change the prev for subsequent node next_ref = p # Finally, set the next pointer in right subtree populateNextRecur(p.left, next_ref) # This code is contributed by Mohit kumar 29 |
C#
// A wrapper over populateNextRecur void populateNext(Node node) { // The first visited node will be the rightmost node // next of the rightmost node will be NULL populateNextRecur(node, next); } /* Set next of all descendants of p by traversing them in reverse Inorder */ void populateNextRecur(Node p, Node next_ref) { if (p != null ) { // First set the next pointer in right subtree populateNextRecur(p.right, next_ref); // Set the next as previously visited node in reverse Inorder p.next = next_ref; // Change the prev for subsequent node next_ref = p; // Finally, set the next pointer in right subtree populateNextRecur(p.left, next_ref); } } // This code is contributed by princiraj1992 |
Javascript
<script> // A wrapper over populateNextRecur function populateNext(node) { // The first visited node will be the rightmost node // next of the rightmost node will be NULL populateNextRecur(node, next); } /* Set next of all descendants of p by traversing them in reverse Inorder */ function populateNextRecur(p, next_ref) { if (p != null ) { // First set the next pointer in right subtree populateNextRecur(p.right, next_ref); // Set the next as previously visited node in reverse Inorder p.next = next_ref; // Change the prev for subsequent node next_ref = p; // Finally, set the next pointer in right subtree populateNextRecur(p.left, next_ref); } } // This code is contributed by importantly. </script> |
时间复杂性： O（n）
方法：
步骤：
- 创建一个数组或ArrayList。
- 将二叉树的按序遍历存储到ArrayList中（要存储节点）。
- 现在遍历数组，并将该节点的下一个指针替换为直接的右节点（数组中的下一个元素，它是顺序的后续元素）。
list.get(i).next = list.get(i+1)
实施：
JAVA
import java.util.ArrayList; //class Node class Node{ int data; Node left,right,next; //constructor for initializing key value and all the //pointers Node( int data){ this .data = data; left = right = next = null ; } } public class Solution { Node root = null ; //list to store inorder sequence ArrayList<Node> list = new ArrayList<>(); //function for populating next pointer to inorder successor void populateNext() { //list = [3,8,10,12] //inorder successor of the present node is the immediate //right node //for ex: inorder successor of 3 is 8 for ( int i= 0 ;i<list.size();i++) { //check if it is the last node //point next of last node(right most) to null if (i != list.size()- 1 ) { list.get(i).next = list.get(i+ 1 ); } else { list.get(i).next = null ; } } // Let us see the populated values Node ptr = root.left.left; while (ptr != null ) { // -1 is printed if there is no successor int print = ptr.next != null ? ptr.next.data : - 1 ; System.out.println( "Next of " + ptr.data + " is: " + print); ptr = ptr.next; } } //insert the inorder into a list to keep track //of the inorder successor void inorder(Node root) { if (root!= null ) { inorder(root.left); list.add(root); inorder(root.right); } } //Driver function public static void main(String args[]) { Solution tree = new Solution(); /* 10 / 8 12 / 3 */ tree.root = new Node( 10 ); tree.root.left = new Node( 8 ); tree.root.right = new Node( 12 ); tree.root.left.left = new Node( 3 ); //function calls tree.inorder(tree.root); tree.populateNext(); } } |
Python3
# class Node class Node: def __init__( self , data): self .data = data; self . next = None ; self .right = None ; self .left = None ; root = None ; # list to store inorder sequence list = []; # function for populating next pointer to inorder successor def populateNext(root): # list = [3,8,10,12] # inorder successor of the present Node is the immediate # right Node # for ex: inorder successor of 3 is 8 for i in range ( len ( list )): # check if it is the last Node # point next of last Node(right most) to None if (i ! = len ( list ) - 1 ): list [i]. next = list [i + 1 ]; else : list [i]. next = None ; # Let us see the populated values ptr = root.left.left; while (ptr ! = None ): # -1 is printed if there is no successor pt = - 1 ; if (ptr. next ! = None ): pt = ptr. next .data; print ( "Next of " , ptr.data , " is: " , pt); ptr = ptr. next ; # insert the inorder into a list to keep track # of the inorder successor def inorder(root): if (root ! = None ): inorder(root.left); list .append(root); inorder(root.right); # Driver function if __name__ = = '__main__' : ''' * 10 / 8 12 / 3 ''' root = Node( 10 ); root.left = Node( 8 ); root.right = Node( 12 ); root.left.left = Node( 3 ); # function calls inorder(root); populateNext(root); # This code is contributed by Rajput-Ji |
C#
using System; using System.Collections.Generic; // class Node public class Node { public int data; public Node left, right, next; // constructor for initializing key value and all the // pointers public Node( int data) { this .data = data; left = right = next = null ; } } public class Solution { Node root = null ; // list to store inorder sequence List<Node> list = new List<Node>(); // function for populating next pointer to inorder successor void populateNext() { // list = [3,8,10,12] // inorder successor of the present node is the immediate // right node // for ex: inorder successor of 3 is 8 for ( int i = 0; i < list.Count; i++) { // check if it is the last node // point next of last node(right most) to null if (i != list.Count - 1) { list[i].next = list[i + 1]; } else { list[i].next = null ; } } // Let us see the populated values Node ptr = root.left.left; while (ptr != null ) { // -1 is printed if there is no successor int print = ptr.next != null ? ptr.next.data : -1; Console.WriteLine( "Next of " + ptr.data + " is: " + print); ptr = ptr.next; } } // insert the inorder into a list to keep track // of the inorder successor void inorder(Node root) { if (root != null ) { inorder(root.left); list.Add(root); inorder(root.right); } } // Driver function public static void Main(String []args) { Solution tree = new Solution(); /* * 10 / 8 12 / 3 */ tree.root = new Node(10); tree.root.left = new Node(8); tree.root.right = new Node(12); tree.root.left.left = new Node(3); // function calls tree.inorder(tree.root); tree.populateNext(); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // class Node class Node { // constructor for initializing key value and all the // pointers constructor(data) { this .data = data; this .left = this .right = this .next = null ; } } let root = null ; // list to store inorder sequence let list = []; // function for populating next pointer to inorder successor function populateNext() { // list = [3,8,10,12] // inorder successor of the present node is the immediate // right node // for ex: inorder successor of 3 is 8 for (let i = 0; i < list.length; i++) { // check if it is the last node // point next of last node(right most) to null if (i != list.length - 1) { list[i].next = list[i + 1]; } else { list[i].next = null ; } } // Let us see the populated values let ptr = root.left.left; while (ptr != null ) { // -1 is printed if there is no successor let print = ptr.next != null ? ptr.next.data : -1; document.write( "Next of " + ptr.data + " is: " + print+ "<br>" ); ptr = ptr.next; } } // insert the inorder into a list to keep track // of the inorder successor function inorder(root) { if (root != null ) { inorder(root.left); list.push(root); inorder(root.right); } } // Driver function /* 10 / 8 12 / 3 */ root = new Node(10); root.left = new Node(8); root.right = new Node(12); root.left.left = new Node(3); // function calls inorder(root); populateNext(); // This code is contributed by avanitrachhadiya2155 </script> |
输出
Next of 3 is: 8Next of 8 is: 10Next of 10 is: 12Next of 12 is: -1
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
