MOOC浙大データ構造—03-樹2 List Leaves(25分)

Gven a tree,you are supposed to list all the leaves in the order of top down,and left to right.
Input Specification:
Each input file contains one test case.For each case,the first line gives a positive integer NN (\le 10≦10)which is the total number of nodes in the tree--and hence the nodes are numbend from 0 to N-1 N−1.The n NN ラインフォロワー、each corespins to a node、and gives the indices of the left and right children of the node.If the child does not exist、a「-」will be put the position.Any pair of children are.separated.space.space.space.space.space.
Output Specification:
For each test case,print in one line all the leaves'indices in the order of top down,and left to right.The e must be exactlyone spactween bertween any adjacent numbers,andのextra spacat the the end of the line.line.
Sample Input:

8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6

Sample Output:

4 1 5

考え方の分析:非常に一般的な問題は、入力に基づいて、ルートノードを見つけ、階層的に巡回し、すべての葉っぱノードをvectorに追加して、出力すればいいです.

#include 
#include 
#include 

#define MAX 10

using namespace std;

typedef struct {
    int left;
    int right;
} Node;

Node node[MAX];
int isRoot[MAX];
vector vec;

/*
void dfsPre( int root ) {
    if( node[root].left == -1 && node[root].right == -1 ) {
        vec.push_back( root );
    }
    if( node[root].left != -1 ) dfsPre( node[root].left );
    if( node[root].right != -1 ) dfsPre( node[root].right );
}
*/

void bfsLevel( int root ) {
    queue q;

    q.push( root );

    while( !q.empty() ) {
        int cur = q.front();
        q.pop();

        if( node[cur].left == -1 && node[cur].right == -1 ) {
            vec.push_back( cur );
        }

        if( node[cur].left != -1 ) q.push( node[cur].left );
        if( node[cur].right != -1 ) q.push( node[cur].right );
    }
}

int main() {
   // freopen( "123.txt", "r", stdin );
    int n;
    scanf( "%d", &n );

    char l, r;

    for( int i = 0; i < n; i++ ) {
        char ch = getchar();
        scanf( "%c %c", &l, &r );

        if( l == '-' ) node[i].left = -1;
        else {
            node[i].left = ( l - '0' );
            isRoot[l - '0'] = 1;
        }

        if( r == '-' ) node[i].right = -1;
        else {
            node[i].right = ( r - '0' );
            isRoot[r - '0'] = 1;
        }
        //printf( "%d %d
", node[i].left, node[i].right );
    }


    int root = -1;
    for( int i = 0; i < n; i++ ) {
        if( isRoot[i] == 0 ) {
            root = i;
            break;
        }
    }

    bfsLevel( root );

    for( int i = 0; i < vec.size(); i++ ) {
        if( i == 0 ) printf( "%d", vec[i] );
        else printf( " %d", vec[i] );
    }
    return 0;
}