List Leaves

问题描述

Given 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 N (≤10) which is the total number of nodes in the tree -- and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds 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 at the position. Any pair of children are separated by a 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. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.

Sample Input:
8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6

Sample Output:
4 1 5

题意：
给你一棵树，按从上到下的顺序打印出叶子节点
输入数据中第一行为节点个数
后面每一行第一个为左孩子 第二个为右孩子

解决思路

这题很简单，将数据存储起来之后，找到根节点，在根节点层序遍历即可

Some Detail Of Function

总体很简单，感觉没什么好说的....

Code

#include<stdio.h>
#include<malloc.h>
#define SIZE 15
typedef struct node {
    int left;
    int right;
    int isRoot;
}Node, *Pnode;
typedef struct queue
{
    Pnode queue[SIZE+1];
    int front;
    int rear;
}Queue, *Pqueue;
Pqueue createQueue(void);
Pnode createList(int length);
int findRoot(Pnode node, int lenght);
void printResult(Pnode p, int length, int root);
int getValue(void);
int main(void) {
    int length;
    int root;
    scanf("%d", &length);
    if(length == 0){
        printf("\n");
        return 0;
    }
    Pnode array = createList(length);
    root = findRoot(array, length);
    printResult(array, length, root);
    return 0;
}
Pnode createList(int length) {
    Pnode array = (Pnode)malloc(sizeof(Node)*length);
    char right;
    char left;
    getchar();
    for (int i = 0; i < length; i++) {
        array[i].isRoot = 1;
        array[i].left = getValue();
        array[i].right = getValue();
    }
    return array;
}
Pqueue createQueue(void) {
    Pqueue p = 0;
    p = (Pqueue)malloc(sizeof(Queue));
    p->front = p->rear = 0;
    return p;
}
int findRoot(Pnode node, int lenght) {
    for (int i = 0; i < lenght; i++) {
        if (node[i].left != -1)
            node[node[i].left].isRoot = 0;
        if (node[i].right != -1)
            node[node[i].right].isRoot = 0;
    }
    for (int j = 0; j < lenght; j++) {
        if (node[j].isRoot == 1)
            return j;
    }
    return 0;
}
Pnode pop(Pqueue queue) {
    Pnode p = queue->queue[queue->rear++];
    return p;
} 
int getValue(void) {
    int count = 0;
    char value;
    char temp[5];
    for (; (value = getchar()) != ' ' && value != '\n';) {
        temp[count++] = value;
    }
    if (count == 2) {
        return 10;
    }
    else if(temp[0] == '-'){
        return -1;
    }
    else {
        return temp[0] - '0';
    }
}
int isEmpty(Pqueue p) {
    if (p->front == p->rear)
        return 1;
    return 0;
}
void push(Pqueue p, Pnode node, int index) {
    node->isRoot = index;
    p->queue[p->front++] = node;
}
void printResult(Pnode p, int length, int root) {
    Pqueue queue = createQueue();
    Pnode check;
    int index = root;
    int count = 0;
    push(queue, &p[index], index);
    for (;!isEmpty(queue);) {
        check = pop(queue);
        index = check->isRoot;
        if (check->left == check->right) {
            count++;
            if(count == 1)
                printf("%d", index);
            else {
                printf(" %d", index);
            }
        }else {
            if (check->left != -1) {
                push(queue, &p[check->left], check->left);
            }
            if (check->right != -1) {
                push(queue, &p[check->right], check->right);
            }
        }
    }
}

Summary

这题挺简单的，但是我不小心翻车了，被卡了很久！！！
因为我在copy我之前写过的代码时，忘记修改，找了好久才发现！！！
关键是我没修改代码，却只有一个测试点没通过？？？
总而言之，大家在copy代码时，一定要注意啊啊啊，这次被搞的快怀疑人生了，总以为自己又有什么极限情况没考虑，最后的结果一脸懵逼...