[알고리즘] 중위 순회

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD

SW Expert Academy

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {

    static class Node {

        int position;
        String value;
        Node left;
        Node right;

        public Node(int position, String value, Node left, Node right) {
            this.position = position;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    static class Tree {

        Node root;

        public Tree(int position, String value) {
            root = getNewNode(position, value);
        }

        public Node getNewNode(int position, String value) {
            return new Node(position, value, null, null);
        }

        public void makeLeftChild(int position, int childPosition, String value) {
            Node childNode = getNewNode(childPosition, value);
            Node parentNode = searchNode(root, position);

            parentNode.left = childNode;
        }

        public void makeRightChild(int position, int childPosition, String value) {
            Node childNode = getNewNode(childPosition, value);
            Node parentNode = searchNode(root, position);

            parentNode.right = childNode;
        }

        public Node getRoot() {
            return root;
        }

        public void inorder(Node curNode) {
            if (curNode.value == null) {
                return;
            }
            inorder(curNode.left);
            sb.append(curNode.value);
            inorder(curNode.right);
        }
        public Node searchNode(Node curNode, int position) {

            if (curNode == null) {
                return null;
            }
            if (curNode.position == position) {
                return curNode;
            }

            Node leftNode = searchNode(curNode.left, position);
            Node rightNode = searchNode(curNode.right, position);
            if (leftNode != null) {
                return leftNode;
            } else {
                return rightNode;
            }
        }
    }
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        for (int testCase = 1; testCase <= 10; testCase++) {
            int N = Integer.parseInt(br.readLine());
            String[] nodes = new String[N + 1];
            int[] lefts = new int[N + 1];
            int[] rights = new int[N + 1];
            int index;
            String value;
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                switch (st.countTokens()) {
                    case 2:
                        index = Integer.parseInt(st.nextToken());
                        value = st.nextToken();
                        nodes[index] = value;
                        break;

                    case 3:
                        index = Integer.parseInt(st.nextToken());
                        value = st.nextToken();
                        nodes[index] = value;
                        lefts[index] = Integer.parseInt(st.nextToken());
                        break;

                    case 4:
                        index = Integer.parseInt(st.nextToken());
                        value = st.nextToken();
                        nodes[index] = value;
                        lefts[index] = Integer.parseInt(st.nextToken());
                        rights[index] = Integer.parseInt(st.nextToken());
                        break;
                }
            }
            Tree tree = new Tree(1, nodes[1]);
            for (int i = 1; i <= N; i++) {
                tree.makeLeftChild(i, lefts[i], nodes[lefts[i]]);
                tree.makeRightChild(i, rights[i], nodes[rights[i]]);
            }

            sb.append("#").append(testCase).append(" ");
            tree.inorder(tree.getRoot());
            sb.append("\n");

        }
        System.out.println(sb);
    }
}

나의 풀이

- 트리를 만들어서 풀었다.

- 입력 받는 걸 제대로 안해서 헤맸는데 디버깅으로 잘 잡았다.

- searchNode 같은 경우 null 값을 반환할 수도 있으므로 그 경우 curNode.을 사용할 수 없다. curNode가 null이 되기 때문이다.

- 이러한 포인트를 잘 잡자!!!