백준 [1991] 트리 순회

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

1991번: 트리 순회

 

트리를 초기화하는 부분에서 많이 헤맸던 문제이다.

 

처음에는 배열로 초기화를 했었다. 그러다보니 부모 노드를 찾을 때 어떻게 접근할지 몰라서 당황스러웠다.

 

초기화가 어려워 다른 풀이를 참고 했는데 부모 노드를 하나 지정한 다음 재귀를 활용하여 초기화를 해주는 방법이 있었다.

트리 순회도 재귀, 초기화도 재귀로 해주는 신기한 문제였다.

 

부모 노드에 자식 노드를 넣어주는 메서드

입력으로 들어온 C, 왼쪽 자식으로 E, 오른쪽 자식으로 F가 예제와 같이 입력되었을 때 과정을 보자

(이미 A의 왼쪽, 오른쪽 자식으로 C가 들어가 있음을 가정하자)

 

temp에 처음엔 A, parent로 C가 들어간다. 

temp.val인 A는 C와 같지 않아서 왼쪽자식과 오른쪽 자식으로 내려간다. (else 문으로 진입)

 

그 다음 A의 왼쪽 자식과 오른쪽 자식에 대해서 탐색을 한다. (재귀 insert 메서드 진입)

 

왼쪽은 B 오른쪽은 C인데 오른쪽 insert()에 진입하면 temp.right이 A의 오른쪽,

즉 C이였으므로 재귀로 들어온 temp.val와 parent 값인 C가 일치한다. (if 문 진입)

 

처음 입력이 C E(leftChild) F(rightChild)로 입력 받았으니까 . 이 아니기 때문에 temp(C 객체)의 left, right 값을 초기화한다.

 

그럼

A.right = C 

- C.left = E

- C.right = F

이렇게 A 객체 하나로 연결이 가능하다.

 

밑은 노드 초기화 메서드 코드이다.

static void insert(TreeNode temp, char parent, char leftChild, char rightChild) {
    // 현재 노드가 부모 노드이면 자식 노드들이 있으면 자식 노드 생성
    if (temp.val == parent) {
        temp.left = (leftChild == '.' ? null : new TreeNode(leftChild, null, null));
        temp.right = (rightChild == '.' ? null : new TreeNode(rightChild, null, null));
    } else {
        // 찾고자 하는 부모 노드가 아니라면 현재 노드의 자식이 찾고자 하는 부모노드가 맞을 때 까지 탐색
        if (temp.left != null) {
            insert(temp.left, parent, leftChild, rightChild);
        }
        if (temp.right != null) {
            insert(temp.right, parent, leftChild, rightChild);
        }
    }
}

 

전위, 중위, 후위 순회를 재귀로 탐색하는 부분은 어렵지 않았으나, 트리 노드들을 초기화하는 방법이 신기했던 문제였다.

 

이를 Map으로 구현해보아도 될 것 같다는 생각도 해보았다. 다음 이런 문제를 복습할 때 이 방법도 고려해보아야겠다.

 

순회를 하는 로직은 재귀를 순회 방법에 따라 어느 노드 부터 먼저 순회를 하고 출력을 할 것인지 호출 순서만 고려해주면 해결할 수 있었다.

 

 

전체 코드

package com.baekjoon.p1991;

import java.io.*;
import java.util.*;

public class Main {

    static StringBuilder sb = new StringBuilder();
    static TreeNode root = new TreeNode('A', null, null);

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            char parent = st.nextToken().charAt(0);
            char leftChild = st.nextToken().charAt(0);
            char rightChild = st.nextToken().charAt(0);

            insert(root, parent, leftChild, rightChild);
        }

        preOrder(root);
        sb.append("\n");
        inOrder(root);
        sb.append("\n");
        postOrder(root);
        sb.append("\n");

        System.out.println(sb);
    }

    static void insert(TreeNode temp, char parent, char leftChild, char rightChild) {
        // 현재 노드가 부모 노드이면 자식 노드들이 있으면 자식 노드 생성
        if (temp.val == parent) {
            temp.left = (leftChild == '.' ? null : new TreeNode(leftChild, null, null));
            temp.right = (rightChild == '.' ? null : new TreeNode(rightChild, null, null));
        } else {
            // 찾고자 하는 부모 노드가 아니라면 현재 노드의 자식이 찾고자 하는 부모노드가 맞을 때 까지 탐색
            if (temp.left != null) {
                insert(temp.left, parent, leftChild, rightChild);
            }
            if (temp.right != null) {
                insert(temp.right, parent, leftChild, rightChild);
            }
        }
    }

    // 전위 순회
    static void preOrder(TreeNode node) {
        if (node == null) {
            return;
        }

        sb.append(node.val);

        preOrder(node.left);

        preOrder(node.right);
    }

    // 중위 순회
    static void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }

        inOrder(node.left);

        sb.append(node.val);

        inOrder(node.right);
    }

    // 후위 순회
    static void postOrder(TreeNode node) {
        if (node == null) {
            return;
        }

        postOrder(node.left);

        postOrder(node.right);

        sb.append(node.val);
    }
}

class TreeNode {
    char val;
    TreeNode left;
    TreeNode right;

    TreeNode(char val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}