[白俊]#1068樹

質問する

ツリーのリーフノードとは、サブノード数が0のノードを指します.
ツリーが付与されると、ノードが削除されます.次に,残りのツリーにプログラムを記述してリーフノードの個数を求める.ノードをクリアすると、ノードとそのすべてのサブノードがツリーから削除されます.
たとえば、次のツリーがあるとします.

現在,リーフノードの個数は3個である.(緑を塗ったノード)このとき、1番をクリアすると次のようになります.黒く塗られたノードは、ツリーから削除されたノードです.

現在、リーフノードの数は1つです.

入力

最初の行は、ツリー内のノードの個数Nを与える.Nは50以下の自然数である.2行目には、0番ノードからN-1番ノード、各ノードの親ノードが表示されます.親(根)-1がいなければ.3行目には、削除するノード番号が表示されます.

しゅつりょく

第1行目の入力が所定のツリーから入力され、所定のノードがクリアされると、リーフノードの個数が出力される.

入力例1

5
-1 0 0 1 1
2

サンプル出力1

2

入力例2

5
-1 0 0 1 1
1

サンプル出力2

1

入力例3

5
-1 0 0 1 1
0

サンプル出力3

0

入力例4

9
-1 0 0 2 2 4 4 6 6
4

サンプル出力4

2

に答える

この問題はdfs(深さ優先探索)アルゴリズムで解くことができる.通常のツリーの問題をチェックしたり、サブノードのみを削除したりする場合を考慮する必要があります.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    static ArrayList<Integer>[] tree;
    static int delete;
    static int ans = 0;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int root = 0;

        tree = new ArrayList[N];
        for(int i=0; i<N; i++)
            tree[i] = new ArrayList<>();

        String[] input = br.readLine().split(" ");
        for(int i=0; i<N; i++) {
            int x = Integer.parseInt(input[i]);

            if(x==-1)
                root = i;

            else
                tree[x].add(i);         //트리 생성
        }

        delete = Integer.parseInt(br.readLine());

        dfs(root, false);       //루트부터 탐색

        System.out.println(ans);
    }

    public static void dfs(int leaf, boolean flag) {

        if(leaf==delete) {
            if(flag)      //부모의 자식 노드가 삭제한 노드 뿐일 때 1 
                ans++;
            return;
        }

        if(tree[leaf].size()==0) {
            ans++;
            return;
        }

        for(int next : tree[leaf]) {
            if(next==delete && tree[leaf].size()==1)    //부모의 자식 노드가 삭제한 노드 뿐일 때 체크
                dfs(next, true);
            else
                dfs(next, flag);
        }
    }
}