Tree #2 Binary Tree to DLL

Writer: Steven, Lee

Date: 4/12, Friday

Purpose: Binary Tree to DLL

Topic: Linked List, Tree

Level: Hard

Percentage: 41.34% have solved this problem

Time: it took me 20 minutes :)

Time Complexity: O(n) worst case

Runtime: 28 ms

한국어 버전은 밑에 있습니다.

* Caution * Before you read the solution that I used, you need to solve this problem by yourself

* Description *

 Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL) In-Place. The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (left most node in BT) must be head node of the DLL.

Input:

 The first line of input contains T denoting the number of testcases. T testcases follow. Each testcase contains two lines of input. The first line contains number of edges. The second line contains relation between nodes.

Output:

 For each testcase, in a new line, print front to end and back to end traversals of DLL.

Your Task:

 You don't have to take input. Complete the function BToDLL that takes node and head as parameter.

Constraints:

1 <=T<= 30
1 <=Number of nodes<= 100
1 <=Data of a node<= 1000

* Example *

#1 ex)

#2 ex)

Input:

2
2
1 2 R 1 3 L
4
10 20 L 10 30 R 20 40 L 20 60 R

Output:

3 1 2 
2 1 3 
40 20 60 10 30 
30 10 60 20 40

Explanation:

Testcase1: The tree is
        1
     /      \
   3       2
So, DLL would be 3<=>1<=>2

Testcase2: The tree is
                           10
                        /        \
                     20         30
                  /       \
               40       60
So, DLL would be 40<=>20<=>60<=>10<=>30

* IDEA (Concept) *

In this time, what kind of skill do we need to use?? I used inorder traversal. Actually, this is really not difficult if you know about it. I've introduced it in the last writing. But Let's have a quick review.

 The only thing you have to know about InOrder Traverse is the direction of it.

1. Traverse the left subtree 

2. Visit the root 

3. Traverse the right subtree.

To sum up, Left -> Root -> Right. That's it !! Then, I am going to give you a simple example. Check it by yourself 

  * Binary  Tree *

              1

            /    \

         2       3

        /        /   \

      4        5    6 

/   \

   7     8

InOrder:   ???????

The answer is on the last of this writing :)

* IDEA (Problem) *

 Let me explain my algorithm. First of all, There are two variables, head which is the head of the doubly linked list and prev which is the last node in the linked list being connected. we are going to traverse the tree with inOrder skill. If the head is null, we need to store the address of the first node we found in it. Also, we have to keep it in prev. Next, another the node we found should be connected with the prev and prev need to be connected to that node. After this, prev will be the node. we just do same the same thing. Let me give you an example.

Here is the example

*  Tree  *                        * DLL *                         * Variables *

             10                                       null                            head = null, prev = null  

            /    \

         12      3

        /     \      \

      25   30    36

   

=> You are on 25. The head is null

Store address of 25 in the head and prev.

*  Tree  *                        * DLL *                         * Variables *

             10                                       25                             head = address of 25, prev = address of 25  

            /    \

         12      3

        /     \      \

      25   30    36

=> You are on 12. The prev is address of 25

Store address of 12 in prev.

*  Tree  *                        * DLL *                         * Variables *

             10                                 25 <=> 12                            prev = address of 12  

            /    \

         12      3

        /     \      \

      25   30    36

=> You are on 30. The prev is address of 12

Store address of 30 in prev.

*  Tree  *                        * DLL *                         * Variables *

             10                          25 <=> 12 <=> 30                     prev = address of 30 

            /    \

         12      3

        /     \      \

      25   30    36

*

*

*

*

=> You are on 36. The prev is address of 3

Store address of 36 in the prev.

*  Tree  *                               * DLL *                                         * Variables *

      10                       25 <=> 12 <=> 30 <=> 10 <=> 3 <=> 36                    prev = address of 36

      /    \

   12      3

   /     \      \

25   30    36

That's it. Hopefully, you understand it :)

(한국어)

 

* 난이도: 어려움 *

* 오직 41.43%만이 이 문제를 풀었습니다. *

* 트리와 연결 리스트가 핵심 부분입니다. *

* 저는 20분 정도가 걸렸습니다. *

* 시간 복잡도는 O(n)입니다 *

* 런타임은 28ms입니다. *

* 주의 *  솔루션을 읽기 전에 스스로 문제를 푸실 수 있어야 합니다.

* 지문 *

이진 트리가 주어진다. 이것을 이중 연결 리스트로 바꾸어라. 즉, 연결 리스트에서 각 노드들의 왼쪽과 오른쪽이 서로 연결이 되야 한다. 이 리스트의 순서는 주어진 이진 트리의 중위 순회를 따른다. 중위 순회의 가장 첫 번째 노드는 연결 리스트의 헤드가 되어야 한다.

입력:

 가장 첫번째 줄에 들어오는 T는 테스트의 수를 의미한다. 각각의 테스트 두개의 인풋이 들어온다. 그 중 첫번째는 간선의 수를 의미한다. 두번째는 노드들의 관계를 나타낸다. 

출력:

  각 테스트마다 이중 리스트의 첫 번째부터 마지막 노드까지 프린트하고 다음 줄에 마지막에서 첫 번째 노드까지 프린트한다. 

해야할 일:

  인풋을 받을 필요는 없다. 함수인 노드와 헤드를 받는 BToDLL 함수만 작성하라.

제한:
1 <=T<= 30
1 <=Number of nodes<= 100
1 <=Data of a node<= 1000

* 예시 *

#1 ex)

( 위에 있는 트리는 이중 리스트로 바뀌어야 한다. )

#2 Ex)  $  이와 같은 형식으로 출력해야 합니다.  $

입력:
2
2
1 2 R 1 3 L
4
10 20 L 10 30 R 20 40 L 20 60 R

출력:
3 1 2 
2 1 3 
40 20 60 10 30 
30 10 60 20 40

설명:

Testcase1: 트리는
        1
     /      \
   3       2
따라서, 이중리스트는 다음과 같다. 3<=>1<=>2

Testcase2: 트리는
                           10
                        /        \
                     20         30
                  /       \
               40       60
따라서, 이중리스트는 다음과 같다. 40<=>20<=>60<=>10<=>30

* 아이디어 (개념) *

 이번에는 어떤 기술을 써야 할까요?? 저는 중위 순회를 사용했습니다. 사실 여러분들이 이 순회를 알고 있으면 어렵지 않게 풀 수 있습니다. 저는 제일 최근 글에서 이에 대해서 설명했습니다. 오늘 다시 한번 더 복습을 해보겠습니다.

 여러분들이 중위 순회에 대해서 알아야 할 점은 이것의 방향입니다.

1. 왼쪽 하위트리를 순회합니다.

2. 루트를 방문합니다. 

3. 오른쪽 하위트리를 순회합니다.

요약해보면 왼쪽 -> 루트 -> 오른쪽입니다. 여러분께 간단한 예시를 드리겠습니다. 스스로 풀어보세요 

    * 이진 트리 *

              1

            /    \

         2       3

        /        /   \

      4        5    6 

/   \

   7     8

중위순회:   ???????

답은 글 마지막에 있습니다 :)

* 아이디어 (문제) *

 제 알고리즘에 대해서 설명하겠습니다. 첫 번째로 변수가 두개 있습니다. head는 이중 리스트의 가장 첫 번째 부분이고 prev는 이중 리스트가 연결되는 중에서 가장 마지막 부분입니다. 중위 순회로 트리를 탐방합니다. 만약 head가 null일 때 우리가 찾는 가장 첫 번째 노드의 주소를 여기에 저장합니다. 또한 그 값을 prev에 저장합니다. 다음으로 우리가 찾은 다른 노드를 prev와 연결합니다 그리고 prev도 이 노드와 연결합니다. 그 후, prev에 node의 주소를 저장합니다. 이 작업을 계속해서 합니다.

 예시입니다.

  *  Tree  *                      * DLL *                         * Variables *

             10                                       null                            head = null, prev = null  

            /    \

         12      3

        /     \      \

      25   30    36

   

=> 25에 있고 head는 null입니다. 

25의 주소값을 head와 prev의 저장합니다.

 *  Tree  *                        * DLL *                         * Variables *

             10                                       25                             head = address of 25, prev = address of 25  

            /    \

         12      3

        /     \      \

      25   30    36

=>  12에 있고 prev는 25의 주소를 가지고 있습니다. 

12의 주소를 prev에 저장합니다.

*  Tree  *                        * DLL *                         * Variables *

             10                                 25 <=> 12                            prev = address of 12  

            /    \

         12      3

        /     \      \

      25   30    36

=> 30에 있고 prev는 12의 주소를 가지고 있습니다. 

30의 주소를 prev에 저장합니다.

*  Tree  *                        * DLL *                         * Variables *

             10                          25 <=> 12 <=> 30                     prev = address of 30 

            /    \

         12      3

        /     \      \

      25   30    36

*

*

*

*

=> 36에 있고 prev는 3의 주소를 가지고 있습니다. 

36의 주소를 prev에 저장합니다.

*  Tree  *                               * DLL *                                         * Variables *

      10                       25 <=> 12 <=> 30 <=> 10 <=> 3 <=> 36                    prev = address of 36

      /    \

   12      3

   /     \      \

25   30    36

수고하셨습니다 ^_^/

* Answer Of Check*

Inorder: 4 -> 2 -> 1 -> 7 -> 5 -> 8 -> 3 -> 6 

중위순회: 4 -> 2 -> 1 -> 7 -> 5 -> 8 -> 3 -> 6 

* Check *

You can check it out here

이 사이트에서 정답의 유무를 확인하실 수 있습니다.

https://practice.geeksforgeeks.org/problems/binary-tree-to-dll/1

 
 
 
import java.util.Scanner;
import java.util.*;
 
class Node2{
    int data;
    Node2 left,right;
    Node2(int d) {data = d; left =right= null; }
}
 
 
class BinaryTreeToDLL{
    
    void inorder(Node2 node){
        if(node==null)
            return ;
        else
            inorder(node.left);
            System.out.print(node.data + " ");
            inorder(node.right);    
    }
    
    
    void printList(Node2 head) {
        Node2 prev = head;
        while (head != null) {
            System.out.print(head.data + " ");
            prev = head;
            head = head.right;
        }
        
        System.out.println();
        while(prev != null){
            System.out.print(prev.data+" ");
            prev = prev.left;
        }
    }
    
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        BinaryTreeToDLL obj = new BinaryTreeToDLL();
 
        int t = sc.nextInt();
        
        while(t>0){
            HashMap<Integer, Node2> hm = new HashMap<Integer, Node2>();
            int n = sc.nextInt();
            
            Node2 root = null;
            
            while(n>0){
                int n1 = sc.nextInt();
                int n2 = sc.nextInt();
                char lr = sc.next().charAt(0);
                
                Node2 parent = hm.get(n1);
                if(parent == null){
                    parent = new Node2(n1);
                    hm.put(n1, parent);
                    if(root == null){
                        root = parent;
                    }
                }
                
                Node2 child = new Node2(n2);
                if(lr == 'L')
                    parent.left = child;
                else
                    parent.right = child;
                
                hm.put(n2,child);
                n--;
            }
            
            Sol g = new Sol();
            Node2 node = g.BToDLL(root);
            obj.printList(node);
            
            t--;
            System.out.println();
        }
    }
}
 
 
 
class Sol{
    
    public static Node2 head, prev;
    
    Sol(){
        head = null;
        prev = null;
    }
    
    Node2 BToDLL(Node2 root){
        if(root == null)
            return root;
        
        BToDLL(root.left);
        
        if(head == null) {
            head = root;
            prev = head;
        }
            
        else {
            root.left = prev;
            prev.right = root;
            prev = root;
        }
        
        BToDLL(root.right);
        
        return head;
    }
 
}