트리 순회 1991

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

어려운 문제가 아님에도 한참을 헤맸다

전위순회 중위순회 후위순회는 다시 볼때마다 새롭다
재귀함수가 아직도 어렵다

재귀함수에 인자를 처음에는

(ArrayList<Integer> RootNode)

로 했었는데 코드가 엄청 길어지고 복잡했었다. 인자를 int 로 NodeId 전달하는 것으로 바꾸니 코드가 확줄었다. 그리고 Node의 자기자신을 재귀함수 안에서 출력하는게 가능해져서 코드가 명확하게 바뀌었다.
RootNode로 받으면 부모의 자식을 찾아서 출력하는 형태였는데 그게 문제였다. 그냥 노드의 id를 받아서 그 id로 자기자신을 출력하도록 바꾸니 코드가 단순해지고 이해하기 쉽게 바뀌었다.

그리고 글자는 숫자로 바꿔서 처리하고 다시 출력할때 글자로 바꿔서 출력하도록 하였다
그래서 ArrayList 에 담고 꺼내기가 편리하였다

O(N)

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

public class Main
{
    private static ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
    private static StringBuilder sb = new StringBuilder();

    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)
        {
            tree.add(new ArrayList<>());
        }

        String[] input = null;

        ArrayList<Integer> node = null;

        for(int i = 0; i < N; ++i)
        {
            input = br.readLine().split(" ");
            node = tree.get(input[0].charAt(0) - 'A');

            if(true == input[1].equals("."))
                node.add(-1);
            else
                node.add(input[1].charAt(0) - 'A');

            if(true == input[2].equals("."))
                node.add(-1);
            else
                node.add(input[2].charAt(0) - 'A');

        }

        recur_preorder(0);
        System.out.println(sb);
        sb.setLength(0);


        recur_midorder(0);
        System.out.println(sb);
        sb.setLength(0);

        recur_postorder(0);
        System.out.println(sb);
        sb.setLength(0);
    }

    public static void recur_preorder(Integer NodeId)
    {
        if(NodeId == -1)
            return;

        ArrayList<Integer> curNode = tree.get(NodeId);

        sb.append((char)(NodeId + 'A'));
        recur_preorder(curNode.get(0));


        recur_preorder(curNode.get(1));

    }

    public static void recur_midorder(Integer NodeId)
    {
        if(NodeId == -1)
            return;

        ArrayList<Integer> curNode = tree.get(NodeId);

        recur_midorder(curNode.get(0));

        sb.append((char)(NodeId + 'A'));

        recur_midorder(curNode.get(1));
    }

    public static void recur_postorder(Integer NodeId)
    {
        if(NodeId == -1)
            return;

        ArrayList<Integer> curNode = tree.get(NodeId);

        recur_postorder(curNode.get(0));

        recur_postorder(curNode.get(1));

        sb.append((char)(NodeId + 'A'));
    }
}