이진 트리를 순환 이중 링크 목록으로 변환
GfG Practice에서 사용해 보세요. 
#practiceLinkDiv { 표시: 없음 !중요; }
산출
산출
#practiceLinkDiv { 표시: 없음 !중요; } 주어진 이진 트리 그것을로 변환 순환 이중 연결 목록 (현재 위치).
- 노드의 왼쪽 포인터와 오른쪽 포인터는 변환된 순환 연결 목록에서 각각 이전 포인터와 다음 포인터로 사용됩니다.
- 목록의 노드 순서는 주어진 이진 트리의 중위 순서와 동일해야 합니다.
- 중위 순회(Inorder Traversal)의 첫 번째 노드는 순환 목록(Circular List)의 헤드 노드여야 합니다.
예:
재귀를 사용하여 이진 트리를 순환 이중 링크 목록으로 변환:
아이디어는 주어진 두 개의 순환 이중 목록을 연결하는 범용 함수를 만드는 것입니다.
문제를 해결하려면 아래 단계를 따르십시오.
- 왼쪽 하위 트리를 순환 DLL로 재귀적으로 변환합니다. 변환된 목록을 왼쪽목록 .
- 오른쪽 하위 트리를 순환 DLL로 재귀적으로 변환합니다. 변환된 목록을 오른쪽목록 .
- 트리의 루트에 대한 원형 연결 리스트를 만들고 왼쪽 및 오른쪽 루트 지점을 자신에게 만듭니다.
- 사슬 같이 잇다 왼쪽목록 단일 루트 노드 목록을 사용합니다.
- 위 단계에서 생성된 목록을 다음과 연결합니다. 오른쪽목록 .
메모: 위의 접근 방식은 Postorder 방식으로 트리를 순회합니다. 우리는 또한 무순서적 방식으로 횡단할 수 있습니다. 먼저 왼쪽 하위 트리와 루트를 연결한 다음 오른쪽 하위 트리에 대해 반복하고 결과를 왼쪽 루트 연결로 연결할 수 있습니다.
두 개의 순환 DLL을 어떻게 연결합니까?
- 왼쪽 목록의 마지막 노드를 가져옵니다. 마지막 노드를 검색하는 것은 헤드의 이전 포인터가 목록의 마지막 노드를 가리키기 때문에 O(1) 작업입니다.
- 오른쪽 목록의 첫 번째 노드와 연결
- 두 번째 목록의 마지막 노드를 가져옵니다.
- 목록의 선두와 연결하십시오.
다음은 위의 아이디어를 구현한 것입니다.
C++ // C++ Program to convert a Binary Tree // to a Circular Doubly Linked List #include using namespace std ; // To represents a node of a Binary Tree struct Node { struct Node * left * right ; int data ; }; // A function that appends rightList at the end // of leftList. Node * concatenate ( Node * leftList Node * rightList ) { // If either of the list is empty // then return the other list if ( leftList == NULL ) return rightList ; if ( rightList == NULL ) return leftList ; // Store the last Node of left List Node * leftLast = leftList -> left ; // Store the last Node of right List Node * rightLast = rightList -> left ; // Connect the last node of Left List // with the first Node of the right List leftLast -> right = rightList ; rightList -> left = leftLast ; // Left of first node points to // the last node in the list leftList -> left = rightLast ; // Right of last node refers to the first // node of the List rightLast -> right = leftList ; return leftList ; } // Function converts a tree to a circular Linked List // and then returns the head of the Linked List Node * bTreeToCList ( Node * root ) { if ( root == NULL ) return NULL ; // Recursively convert left and right subtrees Node * left = bTreeToCList ( root -> left ); Node * right = bTreeToCList ( root -> right ); // Make a circular linked list of single node // (or root). To do so make the right and // left pointers of this node point to itself root -> left = root -> right = root ; // Step 1 (concatenate the left list with the list // with single node i.e. current node) // Step 2 (concatenate the returned list with the // right List) return concatenate ( concatenate ( left root ) right ); } // Display Circular Link List void displayCList ( Node * head ) { cout < < 'Circular Linked List is : n ' ; Node * itr = head ; do { cout < < itr -> data < < ' ' ; itr = itr -> right ; } while ( head != itr ); cout < < ' n ' ; } // Create a new Node and return its address Node * newNode ( int data ) { Node * temp = new Node (); temp -> data = data ; temp -> left = temp -> right = NULL ; return temp ; } // Driver Program to test above function int main () { Node * root = newNode ( 10 ); root -> left = newNode ( 12 ); root -> right = newNode ( 15 ); root -> left -> left = newNode ( 25 ); root -> left -> right = newNode ( 30 ); root -> right -> left = newNode ( 36 ); Node * head = bTreeToCList ( root ); displayCList ( head ); return 0 ; } // This code is contributed by Aditya Kumar (adityakumar129)
C // C Program to convert a Binary Tree // to a Circular Doubly Linked List #include #include // To represents a node of a Binary Tree typedef struct Node { struct Node * left * right ; int data ; } Node ; // A function that appends rightList at the end // of leftList. Node * concatenate ( Node * leftList Node * rightList ) { // If either of the list is empty // then return the other list if ( leftList == NULL ) return rightList ; if ( rightList == NULL ) return leftList ; // Store the last Node of left List Node * leftLast = leftList -> left ; // Store the last Node of right List Node * rightLast = rightList -> left ; // Connect the last node of Left List // with the first Node of the right List leftLast -> right = rightList ; rightList -> left = leftLast ; // Left of first node points to // the last node in the list leftList -> left = rightLast ; // Right of last node refers to the first // node of the List rightLast -> right = leftList ; return leftList ; } // Function converts a tree to a circular Linked List // and then returns the head of the Linked List Node * bTreeToCList ( Node * root ) { if ( root == NULL ) return NULL ; // Recursively convert left and right subtrees Node * left = bTreeToCList ( root -> left ); Node * right = bTreeToCList ( root -> right ); // Make a circular linked list of single node // (or root). To do so make the right and // left pointers of this node point to itself root -> left = root -> right = root ; // Step 1 (concatenate the left list with the list // with single node i.e. current node) // Step 2 (concatenate the returned list with the // right List) return concatenate ( concatenate ( left root ) right ); } // Display Circular Link List void displayCList ( Node * head ) { printf ( 'Circular Linked List is : n ' ); Node * itr = head ; do { printf ( '%d ' itr -> data ); itr = itr -> right ; } while ( head != itr ); printf ( ' n ' ); } // Create a new Node and return its address Node * newNode ( int data ) { Node * temp = ( Node * ) malloc ( sizeof ( Node )); temp -> data = data ; temp -> left = temp -> right = NULL ; return temp ; } // Driver Program to test above function int main () { Node * root = newNode ( 10 ); root -> left = newNode ( 12 ); root -> right = newNode ( 15 ); root -> left -> left = newNode ( 25 ); root -> left -> right = newNode ( 30 ); root -> right -> left = newNode ( 36 ); Node * head = bTreeToCList ( root ); displayCList ( head ); return 0 ; } // This code is contributed by Aditya Kumar (adityakumar129)
Java // Java Program to convert a Binary Tree to a // Circular Doubly Linked List // Node class represents a Node of a Tree class Node { int val ; Node left right ; public Node ( int val ) { this . val = val ; left = right = null ; } } // A class to represent a tree class Tree { Node root ; public Tree () { root = null ; } // concatenate both the lists and returns the head // of the List public Node concatenate ( Node leftList Node rightList ) { // If either of the list is empty then // return the other list if ( leftList == null ) return rightList ; if ( rightList == null ) return leftList ; // Store the last Node of left List Node leftLast = leftList . left ; // Store the last Node of right List Node rightLast = rightList . left ; // Connect the last node of Left List // with the first Node of the right List leftLast . right = rightList ; rightList . left = leftLast ; // left of first node refers to // the last node in the list leftList . left = rightLast ; // Right of last node refers to the first // node of the List rightLast . right = leftList ; // Return the Head of the List return leftList ; } // Method converts a tree to a circular // Link List and then returns the head // of the Link List public Node bTreeToCList ( Node root ) { if ( root == null ) return null ; // Recursively convert left and right subtrees Node left = bTreeToCList ( root . left ); Node right = bTreeToCList ( root . right ); // Make a circular linked list of single node // (or root). To do so make the right and // left pointers of this node point to itself root . left = root . right = root ; // Step 1 (concatenate the left list with the list // with single node i.e. current node) // Step 2 (concatenate the returned list with the // right List) return concatenate ( concatenate ( left root ) right ); } // Display Circular Link List public void display ( Node head ) { System . out . println ( 'Circular Linked List is :' ); Node itr = head ; do { System . out . print ( itr . val + ' ' ); itr = itr . right ; } while ( itr != head ); System . out . println (); } } // Driver Code class Main { public static void main ( String args [] ) { // Build the tree Tree tree = new Tree (); tree . root = new Node ( 10 ); tree . root . left = new Node ( 12 ); tree . root . right = new Node ( 15 ); tree . root . left . left = new Node ( 25 ); tree . root . left . right = new Node ( 30 ); tree . root . right . left = new Node ( 36 ); // head refers to the head of the Link List Node head = tree . bTreeToCList ( tree . root ); // Display the Circular LinkedList tree . display ( head ); } }
Python3 # Python3 Program to convert a Binary # Tree to a Circular Doubly Linked List class newNode : def __init__ ( self data ): self . data = data self . left = self . right = None # A function that appends rightList # at the end of leftList. def concatenate ( leftList rightList ): # If either of the list is empty # then return the other list if ( leftList == None ): return rightList if ( rightList == None ): return leftList # Store the last Node of left List leftLast = leftList . left # Store the last Node of right List rightLast = rightList . left # Connect the last node of Left List # with the first Node of the right List leftLast . right = rightList rightList . left = leftLast # Left of first node points to # the last node in the list leftList . left = rightLast # Right of last node refers to # the first node of the List rightLast . right = leftList return leftList # Function converts a tree to a circular # Linked List and then returns the head # of the Linked List def bTreeToCList ( root ): if ( root == None ): return None # Recursively convert left and # right subtrees left = bTreeToCList ( root . left ) right = bTreeToCList ( root . right ) # Make a circular linked list of single # node (or root). To do so make the # right and left pointers of this node # point to itself root . left = root . right = root # Step 1 (concatenate the left list # with the list with single # node i.e. current node) # Step 2 (concatenate the returned list # with the right List) return concatenate ( concatenate ( left root ) right ) # Display Circular Link List def displayCList ( head ): print ( 'Circular Linked List is :' ) itr = head first = 1 while ( head != itr or first ): print ( itr . data end = ' ' ) itr = itr . right first = 0 print () # Driver Code if __name__ == '__main__' : root = newNode ( 10 ) root . left = newNode ( 12 ) root . right = newNode ( 15 ) root . left . left = newNode ( 25 ) root . left . right = newNode ( 30 ) root . right . left = newNode ( 36 ) head = bTreeToCList ( root ) displayCList ( head ) # This code is contributed by PranchalK
C# // C# Program to convert a Binary Tree // to a Circular Doubly Linked List using System ; // Node class represents a Node of a Tree public class Node { public int val ; public Node left right ; public Node ( int val ) { this . val = val ; left = right = null ; } } // A class to represent a tree public class Tree { internal Node root ; public Tree () { root = null ; } // concatenate both the lists // and returns the head of the List public virtual Node concatenate ( Node leftList Node rightList ) { // If either of the list is empty // then return the other list if ( leftList == null ) { return rightList ; } if ( rightList == null ) { return leftList ; } // Store the last Node of left List Node leftLast = leftList . left ; // Store the last Node of right List Node rightLast = rightList . left ; // Connect the last node of Left List // with the first Node of the right List leftLast . right = rightList ; rightList . left = leftLast ; // left of first node refers to // the last node in the list leftList . left = rightLast ; // Right of last node refers to // the first node of the List rightLast . right = leftList ; // Return the Head of the List return leftList ; } // Method converts a tree to a circular // Link List and then returns the head // of the Link List public virtual Node bTreeToCList ( Node root ) { if ( root == null ) { return null ; } // Recursively convert left // and right subtrees Node left = bTreeToCList ( root . left ); Node right = bTreeToCList ( root . right ); // Make a circular linked list of single // node (or root). To do so make the // right and left pointers of this node // point to itself root . left = root . right = root ; // Step 1 (concatenate the left list with // the list with single node // i.e. current node) // Step 2 (concatenate the returned list // with the right List) return concatenate ( concatenate ( left root ) right ); } // Display Circular Link List public virtual void display ( Node head ) { Console . WriteLine ( 'Circular Linked List is :' ); Node itr = head ; do { Console . Write ( itr . val + ' ' ); itr = itr . right ; } while ( itr != head ); Console . WriteLine (); } } // Driver Code public class GFG { public static void Main ( string [] args ) { // Build the tree Tree tree = new Tree (); tree . root = new Node ( 10 ); tree . root . left = new Node ( 12 ); tree . root . right = new Node ( 15 ); tree . root . left . left = new Node ( 25 ); tree . root . left . right = new Node ( 30 ); tree . root . right . left = new Node ( 36 ); // head refers to the head of the Link List Node head = tree . bTreeToCList ( tree . root ); // Display the Circular LinkedList tree . display ( head ); } } // This code is contributed by Shrikant13
JavaScript < script > // javascript Program to convert a Binary Tree to a // Circular Doubly Linked List // Node class represents a Node of a Tree class Node { constructor ( val ) { this . val = val ; this . left = null ; this . right = null ; } } // A class to represent a var root = null ; // concatenate both the lists and returns the head // of the List function concatenate ( leftList rightList ) { // If either of the list is empty then // return the other list if ( leftList == null ) return rightList ; if ( rightList == null ) return leftList ; // Store the last Node of left List var leftLast = leftList . left ; // Store the last Node of right List var rightLast = rightList . left ; // Connect the last node of Left List // with the first Node of the right List leftLast . right = rightList ; rightList . left = leftLast ; // left of first node refers to // the last node in the list leftList . left = rightLast ; // Right of last node refers to the first // node of the List rightLast . right = leftList ; // Return the Head of the List return leftList ; } // Method converts a to a circular // Link List and then returns the head // of the Link List function bTreeToCList ( root ) { if ( root == null ) return null ; // Recursively convert left and right subtrees var left = bTreeToCList ( root . left ); var right = bTreeToCList ( root . right ); // Make a circular linked list of single node // (or root). To do so make the right and // left pointers of this node point to itself root . left = root . right = root ; // Step 1 (concatenate the left list with the list // with single node i.e. current node) // Step 2 (concatenate the returned list with the // right List) return concatenate ( concatenate ( left root ) right ); } // Display Circular Link List function display ( head ) { document . write ( 'Circular Linked List is :
' ); var itr = head ; do { document . write ( itr . val + ' ' ); itr = itr . right ; } while ( itr != head ); document . write (); } // Driver Code // Build the root = new Node ( 10 ); root . left = new Node ( 12 ); root . right = new Node ( 15 ); root . left . left = new Node ( 25 ); root . left . right = new Node ( 30 ); root . right . left = new Node ( 36 ); // head refers to the head of the Link List var head = bTreeToCList ( root ); // Display the Circular LinkedList display ( head ); // This code contributed by umadevi9616 < /script>
산출
Circular Linked List is : 25 12 30 10 36 15
시간 복잡도: 에) 모든 노드는 최대 한 번만 방문됩니다.
보조 공간: O(log N) 이진 트리이므로 최대 logN 크기까지 커질 수 있는 재귀 호출 스택에 추가 공간이 사용됩니다.
중위 순회를 통해 이진 트리를 순환 이중 링크 목록으로 변환:
아이디어는 이진 트리를 순서대로 순회하는 것입니다. 중위 순회를 수행하는 동안 변수에서 이전에 방문한 노드를 추적합니다. 이전 . 방문한 모든 노드에 대해 다음 노드로 만듭니다. 이전 이 노드의 이전 노드를 다음과 같이 설정합니다. 이전 .
문제를 해결하려면 아래 단계를 따르십시오.
- 먼저 이진 트리를 이중 연결 목록으로 변환하십시오. 이 게시물을 참조하십시오. 주어진 이진 트리를 이중 연결 목록으로 변환 .
- 이제 첫 번째 노드와 마지막 노드를 연결하여 이 이중 연결 목록을 순환 이중 연결 목록으로 변환합니다.
아래는 위의 접근 방식을 구현한 것입니다.
C++ // A C++ program for in-place conversion of Binary Tree to // CDLL #include using namespace std ; /* A binary tree node has - data left and right pointers */ struct Node { int data ; Node * left ; Node * right ; }; // A utility function that converts given binary tree to // a doubly linked list // root --> the root of the binary tree // head --> head of the created doubly linked list Node * BTree2DoublyLinkedList ( Node * root Node ** head ) { // Base case if ( root == NULL ) return root ; // Initialize previously visited node as NULL. This is // static so that the same value is accessible in all // recursive calls static Node * prev = NULL ; // Recursively convert left subtree BTree2DoublyLinkedList ( root -> left head ); // Now convert this node if ( prev == NULL ) * head = root ; else { root -> left = prev ; prev -> right = root ; } prev = root ; // Finally convert right subtree BTree2DoublyLinkedList ( root -> right head ); return prev ; } // A simple recursive function to convert a given Binary // tree to Circular Doubly Linked List using a utility // function root --> Root of Binary Tree tail --> Pointer to // tail node of created circular doubly linked list Node * BTree2CircularDoublyLinkedList ( Node * root ) { Node * head = NULL ; Node * tail = BTree2DoublyLinkedList ( root & head ); // make the changes to convert a DLL to CDLL tail -> right = head ; head -> left = tail ; // return the head of the created CDLL return head ; } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ Node * newNode ( int data ) { Node * new_node = new Node ; new_node -> data = data ; new_node -> left = new_node -> right = NULL ; return ( new_node ); } /* Function to print nodes in a given circular doubly linked * list */ void printList ( Node * head ) { if ( head == NULL ) return ; Node * ptr = head ; do { cout < < ptr -> data < < ' ' ; ptr = ptr -> right ; } while ( ptr != head ); } /* Driver program to test above functions*/ int main () { // Let us create the tree shown in above diagram Node * root = newNode ( 10 ); root -> left = newNode ( 12 ); root -> right = newNode ( 15 ); root -> left -> left = newNode ( 25 ); root -> left -> right = newNode ( 30 ); root -> right -> left = newNode ( 36 ); // Convert to DLL Node * head = BTree2CircularDoublyLinkedList ( root ); // Print the converted list printList ( head ); return 0 ; } // This code was contributed by Abhijeet // Kumar(abhijeet19403)
Java // A Java program for in-place conversion of Binary Tree to // CDLL // A binary tree node has - data left pointer and right // pointer class Node { int data ; Node left right ; public Node ( int data ) { this . data = data ; left = right = null ; } } class BinaryTree { Node root ; // head --> Pointer to head node of created doubly // linked list Node head ; // Initialize previously visited node as NULL. This is // static so that the same value is accessible in all // recursive calls static Node prev = null ; // A simple utility recursive function to convert a // given Binary tree to Doubly Linked List root --> Root // of Binary Tree void BTree2DoublyLinkedList ( Node root ) { // Base case if ( root == null ) return ; // Recursively convert left subtree BTree2DoublyLinkedList ( root . left ); // Now convert this node if ( prev == null ) head = root ; else { root . left = prev ; prev . right = root ; } prev = root ; // Finally convert right subtree BTree2DoublyLinkedList ( root . right ); } // A simple function to convert a given binary tree to // Circular doubly linked list // using a utility function void BTree2CircularDoublyLinkedList ( Node root ) { BTree2DoublyLinkedList ( root ); // make the changes to convert a DLL to CDLL prev . right = head ; head . left = prev ; } /* Function to print nodes in a given doubly linked list */ void printList ( Node node ) { if ( node == null ) return ; Node curr = node ; do { System . out . print ( curr . data + ' ' ); curr = curr . right ; } while ( curr != node ); } // Driver program to test above functions public static void main ( String [] args ) { // Let us create the tree as shown in above diagram BinaryTree tree = new BinaryTree (); tree . root = new Node ( 10 ); tree . root . left = new Node ( 12 ); tree . root . right = new Node ( 15 ); tree . root . left . left = new Node ( 25 ); tree . root . left . right = new Node ( 30 ); tree . root . right . left = new Node ( 36 ); // convert to DLL tree . BTree2CircularDoublyLinkedList ( tree . root ); // Print the converted List tree . printList ( tree . head ); } } // This code has been contributed by Abhijeet // Kumar(abhijeet19403)
Python # A python program for in-place conversion of Binary Tree to DLL # A binary tree node has data left pointers and right pointers class Node : def __init__ ( self val ): self . data = val self . left = None self . right = None # head --> Pointer to head node of created doubly linked list head = None # Initialize previously visited node as NULL. This is # so that the same value is accessible in all recursive # calls prev = None # A simple recursive function to convert a given Binary tree # to Doubly Linked List # root --> Root of Binary Tree def BinaryTree2DoubleLinkedList ( root ): # Base case if ( root == None ): return # Recursively convert left subtree BinaryTree2DoubleLinkedList ( root . left ) # Now convert this node global prev head if ( prev == None ): head = root else : root . left = prev prev . right = root prev = root # Finally convert right subtree BinaryTree2DoubleLinkedList ( root . right ) # Function to print nodes in a given doubly linked list def printList ( node ): while ( node != None ): print ( node . data ) node = node . right # Driver program to test above functions # Let us create the tree as shown in above diagram root = Node ( 10 ) root . left = Node ( 12 ) root . right = Node ( 15 ) root . left . left = Node ( 25 ) root . left . right = Node ( 30 ) root . right . left = Node ( 36 ) # convert to DLL BinaryTree2DoubleLinkedList ( root ) # Print the converted List printList ( head ) # This code is contributed by adityamaharshi21.
C# // A C# program for in-place conversion of Binary Tree to // CDLL using System ; public class Node { public int data ; public Node left right ; public Node ( int data ) { this . data = data ; left = right = null ; } } public class BinaryTree { Node root ; // head --> Pointer to head node of created doubly // linked list Node head ; // Initialize previously visited node as NULL. This is // static so that the same value is accessible in all // recursive calls static Node prev = null ; // A simple utility recursive function to convert a // given Binary tree to Doubly Linked List root --> Root // of Binary Tree void BTree2DoublyLinkedList ( Node root ) { // Base case if ( root == null ) return ; // Recursively convert left subtree BTree2DoublyLinkedList ( root . left ); // Now convert this node if ( prev == null ) head = root ; else { root . left = prev ; prev . right = root ; } prev = root ; // Finally convert right subtree BTree2DoublyLinkedList ( root . right ); } // A simple function to convert a given binary tree to // Circular doubly linked list // using a utility function void BTree2CircularDoublyLinkedList ( Node root ) { BTree2DoublyLinkedList ( root ); // make the changes to convert a DLL to CDLL prev . right = head ; head . left = prev ; } /* Function to print nodes in a given doubly linked list */ void printList ( Node node ) { if ( node == null ) return ; Node curr = node ; do { Console . Write ( curr . data + ' ' ); curr = curr . right ; } while ( curr != node ); } static public void Main () { // Let us create the tree as shown in above diagram BinaryTree tree = new BinaryTree (); tree . root = new Node ( 10 ); tree . root . left = new Node ( 12 ); tree . root . right = new Node ( 15 ); tree . root . left . left = new Node ( 25 ); tree . root . left . right = new Node ( 30 ); tree . root . right . left = new Node ( 36 ); // convert to DLL tree . BTree2CircularDoublyLinkedList ( tree . root ); // Print the converted List tree . printList ( tree . head ); } } // This code is contributed by lokesh(lokeshmvs21).
JavaScript // A javascript program for in-place conversion of Binary Tree to DLL // A binary tree node has data left pointers and right pointers class Node { constructor ( val ) { this . data = val ; this . left = null ; this . right = null ; } } var root ; // head --> Pointer to head node of created doubly linked list var head ; // Initialize previously visited node as NULL. This is // so that the same value is accessible in all recursive // calls var prev = null ; // A simple recursive function to convert a given Binary tree // to Doubly Linked List // root --> Root of Binary Tree function BinaryTree2DoubleLinkedList ( root ) { // Base case if ( root == null ) return ; // Recursively convert left subtree BinaryTree2DoubleLinkedList ( root . left ); // Now convert this node if ( prev == null ) head = root ; else { root . left = prev ; prev . right = root ; } prev = root ; // Finally convert right subtree BinaryTree2DoubleLinkedList ( root . right ); } /* Function to print nodes in a given doubly linked list */ function printList ( node ) { while ( node != null ) { console . log ( node . data + ' ' ); node = node . right ; } } // Driver program to test above functions // Let us create the tree as shown in above diagram root = new Node ( 10 ); root . left = new Node ( 12 ); root . right = new Node ( 15 ); root . left . left = new Node ( 25 ); root . left . right = new Node ( 30 ); root . right . left = new Node ( 36 ); // convert to DLL BinaryTree2DoubleLinkedList ( root ); // Print the converted List printList ( head ); // This code is contributed by ishankhandelwals.
산출
25 12 30 10 36 15
시간 복잡도: O(N) 모든 노드는 최대 한 번만 방문됩니다.
보조 공간: 오(로그 N) 추가 공간은 최대 logN 크기까지 증가할 수 있는 재귀 함수 호출 스택에 사용됩니다.
이 접근 방식은 다음에 의해 기여되었습니다. 아비지트 쿠마르
