[백준] 1991번 : 트리 순회 - JAVA [자바]

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

---

이 문제는 트리 문제이다.

먼저 노드에 대한 클래스를 정의한다.

private static class Node {
	char value;
    Node left;
    Node right;
    
    public Node(char value) {
    	this.value = value;
        this.left = null;
        this.right = null;
	}
}

그 후 'A' 부터 시작한다고 하였으니 A 노드를 시작으로 하는 노드를 생성한다.

Node head = new Node('A');

그 후 입력을 받으면서 A 노드에 이어서 추가한다.

for (int n = 0; n < N; n++) {
	String line = br.readLine();
    String[] split = line.split(" ");
    char value = split[0].charAt(0);
    char left = split[1].charAt(0);
    char right = split[2].charAt(0);

	insertNode(head, value, left, right);
}

노드를 추가하는 로직을 살펴보자.

public static void insertNode(Node root, char value, char left, char right) {
	// 현재 노드가 이 노드에 대한 정보가 맞는지 value를 통해 확인
    if (root.value == value) {
    	// 맞다면 이 노드의 정보를 수정
        if (left != '.') {
        	root.left = new Node(left);
		}
        if (right != '.') {
        	root.right = new Node(right);
		}
	} 
    // 현재 노드가 아니라면 현재 노드의 왼쪽 혹은 오른쪽 자식이 있다면 그 자식을 root로 해서 재귀
    else {
    	if (root.left != null) insertNode(root.left, value, left, right);
        if (root.right != null) insertNode(root.right, value, left, right);
	}
}

1. 먼저 현재 root 노드와 입력을 받아서 정보를 업데이트 하려고 하는 노드의 value를 비교한다.
2. 이때 서로 value가 같다면 이 root 노드의 정보를 업데이트 해준다.
3. 만약 서로 같지 않다면 root 노드의 자식 노드들을 살펴본다.
4. 현재 입력을 받아서 정보를 업데이트 하려고 하는 노드가 root의 자식 노드들 일 수 있으니 insertNode 함수에 root 노드의 자식 노드를 root 인자로 넘겨주어서 재귀적으로 다시 1 번을 반복하여 정보를 업데이트 한다.

---

public class bj1991 {

    public static int N;
    public static StringBuilder sb = new StringBuilder();

    public static void insertNode(Node root, char value, char left, char right) {
        // 현재 노드가 이 노드에 대한 정보가 맞는지 value를 통해 확인
        if (root.value == value) {
            // 맞다면 이 노드의 정보를 수정
            if (left != '.') {
                root.left = new Node(left);
            }
            if (right != '.') {
                root.right = new Node(right);
            }
        } // 현재 노드가 아니라면 현재 노드의 왼쪽 혹은 오른쪽 자식이 있다면 그 자식을 root로 해서 재귀
        else {
            if (root.left != null) insertNode(root.left, value, left, right);
            if (root.right != null) insertNode(root.right, value, left, right);
        }

    }

    public static void preorder(Node node) {
        if (node == null) return;
        sb.append(node.value);
        preorder(node.left);
        preorder(node.right);
    }

    public static void inorder(Node node) {
        if (node == null) return;
        inorder(node.left);
        sb.append(node.value);
        inorder(node.right);
    }

    public static void postorder(Node node) {
        if (node == null) return;
        postorder(node.left);
        postorder(node.right);
        sb.append(node.value);
    }

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        Node head = new Node('A');

        for (int n = 0; n < N; n++) {
            String line = br.readLine();
            String[] split = line.split(" ");
            char value = split[0].charAt(0);
            char left = split[1].charAt(0);
            char right = split[2].charAt(0);

            insertNode(head, value, left, right);
        }

        preorder(head);
        sb.append("\n");
        inorder(head);
        sb.append("\n");
        postorder(head);

        bw.write(sb + "");

        bw.flush();
        bw.close();
        br.close();
    }

    private static class Node {
        char value;
        Node left;
        Node right;

        public Node(char value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

}