[JAVA] 백준 22856번 【G4.트리 순회】

문제

22856번: 트리 순회

 

풀이

1️⃣ 트리 클래스를 정의한 풀이

💡 떠오른 Idea

처음에는 이 문제에서 정의한 유사 중위 순회를 똑같이 구현해야하나 고민했었지만, 그러지 않고 쉽게 해결할 수 있었다.

이 유사 중위 순회의 특징은 트리에서 제일 오른쪽 간선은 한번만 지나가게 된다는 특징이 있다.

따라서, 가장 오른쪽 자식만 지나가게끔 하는 순회를 정의하여 노드의 개수를 구했고

간선의 개수는 노드의 개수 -1 임을 이용하여 편도 간선의 개수를 구할 수 있었다.

그리고 (전체 노드의 개수 -1)*2 한 값은 전체 간선을 왕복 간선으로 간주했을때 개수이므로

전체 간선을 왕복으로 생각한 개수에 편도 간선의 개수를 차감해주면 답이 나온다.

 

public class Main {
    static int oneWay;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        TreeNode[] nodes = new TreeNode[N + 1];
        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            int parent = Integer.parseInt(input[0]);
            int left = Integer.parseInt(input[1]);
            TreeNode leftNode = getNode(nodes, left);
            int right = Integer.parseInt(input[2]);
            TreeNode rightNode = getNode(nodes, right);

            TreeNode parentNode = getNode(nodes, parent);
            parentNode.left = leftNode;
            parentNode.right = rightNode;
        }

        order(nodes[1]);
        System.out.println((N - 1) * 2 - (oneWay - 1));
    }

    private static void order(TreeNode node) {
        if (node == null) {
            return;
        }
        oneWay++;
        order(node.right);

    }

    private static TreeNode getNode(TreeNode[] nodes, int idx) {
        TreeNode node;

        if (idx == -1) {
            return null;
        }

        if (nodes[idx] == null) {
            node = new TreeNode(idx);
            nodes[idx] = node;
        } else {
            node = nodes[idx];
        }
        return node;
    }


    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;


        public TreeNode(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }
}

 

결과