백준 5639 이진 검색 트리(JAVA)

https://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

 

 

풀이)

 

풀이1

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main_BJ_5639_이진검색트리 {
    static class Node{
        int num;
        Node left, right;

        public Node(int num) {
            this.num = num;
        }

        public Node(int num, Node left, Node right) {
            this.num = num;
            this.left = left;
            this.right = right;
        }

        void insert(int n){
            if(n < this.num){
                if(this.left == null)
                    this.left = new Node(n);
                else this.left.insert(n);
            }
            else{
                if(this.right == null)
                    this.right = new Node(n);
                else this.right.insert(n);
            }
        }//insert
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Node root = new Node(Integer.parseInt(br.readLine()));
        while(true){
            String str = br.readLine();
            if(str == null || str.equals(""))
                break;
            int node = Integer.parseInt(str);
            root.insert(node);
        }
        postorder(root);
    }//main

    private static void postorder(Node node){
        if(node == null)
            return;

        postorder(node.left);
        postorder(node.right);
        System.out.println(node.num);
    }//postorder
}

첫 번째는 Node 클래스를 선언해서 순서대로 담고, postorder 순으로 출력하기!!

가장 흔히 생각할 수 있는 방법이다.

 

 

 

풀이2)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main_BJ_5639_이진검색트리2 {
    static ArrayList<Integer> tree;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tree = new ArrayList<>();
        while(true){
            String str = br.readLine();
            if(str == null || str.equals(""))
                break;

            tree.add(Integer.parseInt(str));
        }
        postorder(0, tree.size()-1);
    }//main
    private static void postorder(int index, int end){
        if(index > end)
            return;

        int mid = index+1;
        while(mid<=end && tree.get(mid) < tree.get(index))
            mid++;
        postorder(index+1, mid-1);
        postorder(mid, end);
        System.out.println(tree.get(index));
    }//postorder
}
/*
50
30
24
5
28
45
98
52
60

index: 0  end: 8  mid: 6
index: 1  end: 5  mid: 5 (left)
index: 2  end: 4  mid: 4 (left)
index: 3  end: 3  mid: 4 (left)
index: 4  end: 3 (left)
index: 4  end: 3 (right)
print tree(index) = 5
index: 4  end: 4  mid: 5 (right)
index: 5  end: 4 (left)
index: 5  end: 4 (right)
print tree(index) = 28
print tree(index) = 24
index: 6  end: 5 (left)
print tree(index) = 45
...
 */

ArrayList 또는 배열에 차례대로 담고, subtree를 구분하기 위해 중간 지점을 찾아가며 postorder 순으로 출력!

왼쪽 subtree, 오른쪽 subtree 순으로 찾고, 본인을 출력하면 된다.

 

 

• 깨달은 점
  
  • 입력이 어느정도인지 정해지지 않은 경우 null이나 ""과 같을 경우를 사용하면 된다.
  • Scanner는 hasNext()를 사용하면 된다
• 잘 못했던 점
  • 트리를 탐색할 때 중간 지점을 찾아 subtree를 재귀로 탐색하는 방법 -> 헷갈려서 일일히 디버깅하면서 쳐봄..ㅠ

 

막상 풀어보니 별거 아닌것 같은데 헷갈렸던 문제였다.

다시 풀어봐야지!

 

 

 

참고한 블로그

https://girawhale.tistory.com/59

[백준] 5639번: 이진 검색 트리 - JAVA