<Algorithm> 73. 1068번 트리

1. 1068번 트리

• 트리의 단말노드를 찾는 문제

• 트리문제를 접근할때 한쪽에만 자식들이 달려있는 경우를 생각해야 될 것 같다.

• 이진트리인줄 알고 접근했다가 꽤 시간이 걸린문제 이진트리라고 명시가 안되있는 경우 자식이 꼭 2개까지만 있는 경우는 없다.

• 노드가 삭제될때 상위노드의 자식이 하나 뿐이였다면 부모가 단말노드가 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static ArrayList<Node>[] alists;
    static int count = 0;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        alists = new ArrayList[N]; 
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for(int i = 0; i < N; i ++) {
            alists[i] = new ArrayList<>();
        }
        
        int root = 0;
        
        for(int i = 0; i < N; i ++) {
            int parent = Integer.parseInt(st.nextToken());
            if(parent != -1)
                alists[parent].add(new Node(i)); 
            else
                root = i;
        }
        
        int remove = Integer.parseInt(br.readLine());
 
        searchTree(root, remove, 0);
        System.out.println(count);
        
    }
    
    private static void searchTree(int vertax, int remove, int pNodeCount) {
        if(vertax == remove) {
            if(pNodeCount == 1) {
                count++;
            }
            return;
        }
        
        if(alists[vertax].size()==0) {
            count ++;
            return;
        }
        
        for(Node node:alists[vertax]) {
            searchTree(node.vertax, remove, alists[vertax].size());
        }
    
        /*if(alists[vertax].size() == 1) {
            searchTree(alists[vertax].get(0).vertax,remove,1);
        }else {
            
            searchTree(alists[vertax].get(0).vertax,remove,2);
            searchTree(alists[vertax].get(1).vertax,remove,2);            
        }*/
        
    }
}
 
class Node{
    int vertax;
 
    public Node(int vertax) {
        super();
        this.vertax = vertax;
    }
    
}

참고 & 출처