이진 트리 뒤집기
주어진 이진 트리 임무는 튀기다 이진 트리는 올바른 방향 ㄴ 그건 시계 방향으로.
입력:
산출:
설명: 뒤집기 작업에서 가장 왼쪽 노드는 뒤집힌 트리의 루트가 되고 그 부모는 오른쪽 자식이 되고 오른쪽 형제는 왼쪽 자식이 되며 모든 왼쪽 노드에 대해 동일한 작업이 재귀적으로 수행되어야 합니다.
목차
[예상 접근 방식 - 1] 재귀 활용 - O(n) 시간과 O(n) 공간
아이디어는 재귀적으로 교환하여 이진 트리를 뒤집습니다. 왼쪽 그리고 오른쪽 각 노드의 하위 트리 뒤집힌 후에는 트리의 구조가 반전되고 트리의 새로운 루트가 생성됩니다. 뒤집힌 나무 원래의 가장 왼쪽 리프 노드가 됩니다.
아래는 주요 내용입니다 회전 코드 하위 트리의:
- 루트->왼쪽->왼쪽 = 루트->오른쪽
- 루트->왼쪽->오른쪽 = 루트
- 루트->왼쪽 = NULL
- 루트->오른쪽 = NULL
다음은 위의 접근 방식을 구현한 것입니다.
C++ // C++ program to flip a binary tree // using recursion #include using namespace std ; class Node { public : int data ; Node * left * right ; Node ( int x ) { data = x ; left = right = nullptr ; } }; // method to flip the binary tree iteratively Node * flipBinaryTree ( Node * root ) { // Base cases if ( root == nullptr ) return root ; if ( root -> left == nullptr && root -> right == nullptr ) return root ; // Recursively call the same method Node * flippedRoot = flipBinaryTree ( root -> left ); // Rearranging main root Node after returning // from recursive call root -> left -> left = root -> right ; root -> left -> right = root ; root -> left = root -> right = nullptr ; return flippedRoot ; } // Iterative method to do level order traversal // line by line void printLevelOrder ( Node * root ) { // Base Case if ( root == nullptr ) return ; // Create an empty queue for // level order traversal queue < Node *> q ; // Enqueue Root and initialize height q . push ( root ); while ( 1 ) { // nodeCount (queue size) indicates number // of nodes at current level. int nodeCount = q . size (); if ( nodeCount == 0 ) break ; // Dequeue all nodes of current level and // Enqueue all nodes of next level while ( nodeCount > 0 ) { Node * node = q . front (); cout < < node -> data < < ' ' ; q . pop (); if ( node -> left != nullptr ) q . push ( node -> left ); if ( node -> right != nullptr ) q . push ( node -> right ); nodeCount -- ; } cout < < endl ; } } int main () { // Make a binary tree // // 1 // / // 2 3 // / // 4 5 Node * root = new Node ( 1 ); root -> left = new Node ( 2 ); root -> right = new Node ( 3 ); root -> right -> left = new Node ( 4 ); root -> right -> right = new Node ( 5 ); root = flipBinaryTree ( root ); printLevelOrder ( root ); return 0 ; }
Java // Java program to flip a binary tree // using recursion class Node { int data ; Node left right ; Node ( int x ) { data = x ; left = right = null ; } } class GfG { // Method to flip the binary tree static Node flipBinaryTree ( Node root ) { // Base cases if ( root == null ) return root ; if ( root . left == null && root . right == null ) return root ; // Recursively call the same method Node flippedRoot = flipBinaryTree ( root . left ); // Rearranging main root Node after returning // from recursive call root . left . left = root . right ; root . left . right = root ; root . left = root . right = null ; return flippedRoot ; } // Iterative method to do level order // traversal line by line static void printLevelOrder ( Node root ) { // Base Case if ( root == null ) return ; // Create an empty queue for level // order traversal java . util . Queue < Node > q = new java . util . LinkedList <> (); // Enqueue Root and initialize height q . add ( root ); while ( ! q . isEmpty ()) { // nodeCount (queue size) indicates // number of nodes at current level int nodeCount = q . size (); // Dequeue all nodes of current level // and Enqueue all nodes of next level while ( nodeCount > 0 ) { Node node = q . poll (); System . out . print ( node . data + ' ' ); if ( node . left != null ) q . add ( node . left ); if ( node . right != null ) q . add ( node . right ); nodeCount -- ; } System . out . println (); } } public static void main ( String [] args ) { // Make a binary tree // // 1 // / // 2 3 // / // 4 5 Node root = new Node ( 1 ); root . left = new Node ( 2 ); root . right = new Node ( 3 ); root . right . left = new Node ( 4 ); root . right . right = new Node ( 5 ); root = flipBinaryTree ( root ); printLevelOrder ( root ); } }
Python # Python program to flip a binary # tree using recursion class Node : def __init__ ( self x ): self . data = x self . left = None self . right = None def flipBinaryTree ( root ): # Base cases if root is None : return root if root . left is None and root . right is None : return root # Recursively call the same method flippedRoot = flipBinaryTree ( root . left ) # Rearranging main root Node after returning # from recursive call root . left . left = root . right root . left . right = root root . left = root . right = None return flippedRoot # Iterative method to do level order # traversal line by line def printLevelOrder ( root ): # Base Case if root is None : return # Create an empty queue for # level order traversal queue = [] queue . append ( root ) while queue : nodeCount = len ( queue ) while nodeCount > 0 : node = queue . pop ( 0 ) print ( node . data end = ' ' ) if node . left is not None : queue . append ( node . left ) if node . right is not None : queue . append ( node . right ) nodeCount -= 1 print () if __name__ == '__main__' : # Make a binary tree # # 1 # / # 2 3 # / # 4 5 root = Node ( 1 ) root . left = Node ( 2 ) root . right = Node ( 3 ) root . right . left = Node ( 4 ) root . right . right = Node ( 5 ) root = flipBinaryTree ( root ) printLevelOrder ( root )
C# // C# program to flip a binary tree // using recursion using System ; using System.Collections.Generic ; class Node { public int data ; public Node left right ; public Node ( int x ) { data = x ; left = right = null ; } } class GfG { // Method to flip the binary tree static Node FlipBinaryTree ( Node root ) { if ( root == null ) return root ; if ( root . left == null && root . right == null ) return root ; // Recursively call the same method Node flippedRoot = FlipBinaryTree ( root . left ); // Rearranging main root Node after returning // from recursive call root . left . left = root . right ; root . left . right = root ; root . left = root . right = null ; return flippedRoot ; } // Iterative method to do level order // traversal line by line static void PrintLevelOrder ( Node root ) { if ( root == null ) return ; // Create an empty queue for level // order traversal Queue < Node > q = new Queue < Node > (); // Enqueue Root and initialize height q . Enqueue ( root ); while ( q . Count > 0 ) { // nodeCount (queue size) indicates // number of nodes at current level int nodeCount = q . Count ; // Dequeue all nodes of current level // and Enqueue all nodes of next level while ( nodeCount > 0 ) { Node node = q . Dequeue (); Console . Write ( node . data + ' ' ); if ( node . left != null ) q . Enqueue ( node . left ); if ( node . right != null ) q . Enqueue ( node . right ); nodeCount -- ; } Console . WriteLine (); } } static void Main ( string [] args ) { // Make a binary tree // // 1 // / // 2 3 // / // 4 5 Node root = new Node ( 1 ); root . left = new Node ( 2 ); root . right = new Node ( 3 ); root . right . left = new Node ( 4 ); root . right . right = new Node ( 5 ); root = FlipBinaryTree ( root ); PrintLevelOrder ( root ); } }
JavaScript // JavaScript program to flip a binary // tree using recursion class Node { constructor ( x ) { this . data = x ; this . left = null ; this . right = null ; } } // Method to flip the binary tree function flipBinaryTree ( root ) { if ( root === null ) return root ; if ( root . left === null && root . right === null ) return root ; // Recursively call the same method const flippedRoot = flipBinaryTree ( root . left ); // Rearranging main root Node after returning // from recursive call root . left . left = root . right ; root . left . right = root ; root . left = root . right = null ; return flippedRoot ; } // Iterative method to do level order traversal // line by line function printLevelOrder ( root ) { if ( root === null ) return ; // Create an empty queue for level // order traversal const queue = [ root ]; while ( queue . length > 0 ) { let nodeCount = queue . length ; while ( nodeCount > 0 ) { const node = queue . shift (); console . log ( node . data + ' ' ); if ( node . left !== null ) queue . push ( node . left ); if ( node . right !== null ) queue . push ( node . right ); nodeCount -- ; } console . log (); } } // Make a binary tree // // 1 // / // 2 3 // / // 4 5 const root = new Node ( 1 ); root . left = new Node ( 2 ); root . right = new Node ( 3 ); root . right . left = new Node ( 4 ); root . right . right = new Node ( 5 ); const flippedRoot = flipBinaryTree ( root ); printLevelOrder ( flippedRoot );
산출
2 3 1 4 5
[예상 접근법 - 2] 반복적 접근 방식 - O(n) 시간과 O(n) 공간
그만큼 반복적인 솔루션 와 동일한 접근 방식을 따릅니다. 재귀적 우리가 주목해야 할 유일한 것은 절약 노드 정보는 덮어썼다 .
다음은 위의 접근 방식을 구현한 것입니다.
C++ // C++ program to flip a binary tree using // iterative approach #include using namespace std ; class Node { public : int data ; Node * left * right ; Node ( int x ) { data = x ; left = right = nullptr ; } }; // Method to flip the binary tree iteratively Node * flipBinaryTree ( Node * root ) { // intiliazing the pointers to do the // swapping and storing states Node * curr = root * next = nullptr * prev = nullptr * ptr = nullptr ; while ( curr != nullptr ) { // pointing the next pointer to the // current next of left next = curr -> left ; // making the right child of prev // as curr left child curr -> left = ptr ; // storign the right child of // curr in temp ptr = curr -> right ; curr -> right = prev ; prev = curr ; curr = next ; } return prev ; } // Iterative method to do level order traversal // line by line void printLevelOrder ( Node * root ) { // Base Case if ( root == nullptr ) return ; // Create an empty queue for level // order traversal queue < Node *> q ; // Enqueue Root and // initialize height q . push ( root ); while ( 1 ) { // nodeCount (queue size) indicates number // of nodes at current level. int nodeCount = q . size (); if ( nodeCount == 0 ) break ; // Dequeue all nodes of current level and // Enqueue all nodes of next level while ( nodeCount > 0 ) { Node * node = q . front (); cout < < node -> data < < ' ' ; q . pop (); if ( node -> left != nullptr ) q . push ( node -> left ); if ( node -> right != nullptr ) q . push ( node -> right ); nodeCount -- ; } cout < < endl ; } } int main () { // Make a binary tree // // 1 // / // 2 3 // / // 4 5 Node * root = new Node ( 1 ); root -> left = new Node ( 2 ); root -> right = new Node ( 3 ); root -> right -> left = new Node ( 4 ); root -> right -> right = new Node ( 5 ); root = flipBinaryTree ( root ); printLevelOrder ( root ); return 0 ; }
Java // Java program to flip a binary tree // using iterative approach class Node { int data ; Node left right ; Node ( int x ) { data = x ; left = right = null ; } } class GfG { // Method to flip the binary tree static Node flipBinaryTree ( Node root ) { // Initializing the pointers to do the // swapping and storing states Node curr = root ; Node next = null ; Node prev = null ; Node ptr = null ; while ( curr != null ) { // Pointing the next pointer to // the current next of left next = curr . left ; // Making the right child of // prev as curr left child curr . left = ptr ; // Storing the right child // of curr in ptr ptr = curr . right ; curr . right = prev ; prev = curr ; curr = next ; } return prev ; } // Iterative method to do level order // traversal line by line static void printLevelOrder ( Node root ) { if ( root == null ) return ; // Create an empty queue for level // order traversal java . util . Queue < Node > q = new java . util . LinkedList <> (); // Enqueue Root and initialize // height q . add ( root ); while ( ! q . isEmpty ()) { // nodeCount (queue size) indicates // number of nodes at current level int nodeCount = q . size (); // Dequeue all nodes of current level // and Enqueue all nodes of next level while ( nodeCount > 0 ) { Node node = q . poll (); System . out . print ( node . data + ' ' ); if ( node . left != null ) q . add ( node . left ); if ( node . right != null ) q . add ( node . right ); nodeCount -- ; } System . out . println (); } } public static void main ( String [] args ) { // Make a binary tree // // 1 // / // 2 3 // / // 4 5 Node root = new Node ( 1 ); root . left = new Node ( 2 ); root . right = new Node ( 3 ); root . right . left = new Node ( 4 ); root . right . right = new Node ( 5 ); root = flipBinaryTree ( root ); printLevelOrder ( root ); } }
Python # Python program to flip a binary tree # using iterative approach class Node : def __init__ ( self x ): self . data = x self . left = None self . right = None # Method to flip the binary tree # iteratively def flip_binary_tree ( root ): # Initializing the pointers to do # the swapping and storing states curr = root next = None prev = None ptr = None while curr is not None : # Pointing the next pointer to the # current next of left next = curr . left # Making the right child of prev # as curr left child curr . left = ptr # Storing the right child of # curr in ptr ptr = curr . right curr . right = prev prev = curr curr = next return prev # Iterative method to do level order # traversal line by line def printLevelOrder ( root ): if root is None : return # Create an empty queue for # level order traversal queue = [] queue . append ( root ) while queue : nodeCount = len ( queue ) while nodeCount > 0 : node = queue . pop ( 0 ) print ( node . data end = ' ' ) if node . left is not None : queue . append ( node . left ) if node . right is not None : queue . append ( node . right ) nodeCount -= 1 print () if __name__ == '__main__' : # Make a binary tree # # 1 # / # 2 3 # / # 4 5 root = Node ( 1 ) root . left = Node ( 2 ) root . right = Node ( 3 ) root . right . left = Node ( 4 ) root . right . right = Node ( 5 ) root = flip_binary_tree ( root ) printLevelOrder ( root )
C# // C# program to flip a binary tree // using iterative approach using System ; using System.Collections.Generic ; class Node { public int data ; public Node left right ; public Node ( int x ) { data = x ; left = right = null ; } } class GfG { // Method to flip the binary tree static Node FlipBinaryTree ( Node root ) { // Initializing the pointers to // do the swapping and storing states Node curr = root ; Node next = null ; Node prev = null ; Node ptr = null ; while ( curr != null ) { // Pointing the next pointer to // the current next of left next = curr . left ; // Making the right child of prev // as curr left child curr . left = ptr ; // Storing the right child // of curr in ptr ptr = curr . right ; curr . right = prev ; prev = curr ; curr = next ; } return prev ; } // Iterative method to do level order // traversal line by line static void PrintLevelOrder ( Node root ) { if ( root == null ) return ; // Create an empty queue for // level order traversal Queue < Node > q = new Queue < Node > (); // Enqueue Root and initialize height q . Enqueue ( root ); while ( q . Count > 0 ) { // nodeCount (queue size) indicates // number of nodes at current level int nodeCount = q . Count ; // Dequeue all nodes of current level // and Enqueue all nodes of next level while ( nodeCount > 0 ) { Node node = q . Dequeue (); Console . Write ( node . data + ' ' ); if ( node . left != null ) q . Enqueue ( node . left ); if ( node . right != null ) q . Enqueue ( node . right ); nodeCount -- ; } Console . WriteLine (); } } static void Main ( string [] args ) { // Make a binary tree // // 1 // / // 2 3 // / // 4 5 Node root = new Node ( 1 ); root . left = new Node ( 2 ); root . right = new Node ( 3 ); root . right . left = new Node ( 4 ); root . right . right = new Node ( 5 ); root = FlipBinaryTree ( root ); PrintLevelOrder ( root ); } }
JavaScript // JavaScript program to flip a binary // tree using iterative approach class Node { constructor ( x ) { this . data = x ; this . left = null ; this . right = null ; } } function flipBinaryTree ( root ) { // Initializing the pointers to do the // swapping and storing states let curr = root ; let next = null ; let prev = null ; let ptr = null ; while ( curr !== null ) { // Pointing the next pointer to the // current next of left next = curr . left ; // Making the right child of prev // as curr left child curr . left = ptr ; // Storing the right child of // curr in ptr ptr = curr . right ; curr . right = prev ; prev = curr ; curr = next ; } return prev ; } // Iterative method to do level order // traversal line by line function printLevelOrder ( root ) { if ( root === null ) return ; // Create an empty queue for // level order traversal const queue = [ root ]; while ( queue . length > 0 ) { let nodeCount = queue . length ; while ( nodeCount > 0 ) { const node = queue . shift (); console . log ( node . data + ' ' ); if ( node . left !== null ) queue . push ( node . left ); if ( node . right !== null ) queue . push ( node . right ); nodeCount -- ; } console . log (); } } // Make a binary tree // // 1 // / // 2 3 // / // 4 5 const root = new Node ( 1 ); root . left = new Node ( 2 ); root . right = new Node ( 3 ); root . right . left = new Node ( 4 ); root . right . right = new Node ( 5 ); const flippedRoot = flipBinaryTree ( root ); printLevelOrder ( flippedRoot );
산출
2 3 1 4 5
