03-树2 List Leaves

03-树2 List Leaves

分数 25
作者 陈越
单位 浙江大学

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

代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
C++ (g++)

思路：

本题要求我们对树进行层序遍历
自顶向下，从左向右，一层一层的遍历。
建树——》寻找根节点——》寻找叶子节点——》格式化输出。
这里我们用四个函数来实现。
void TreeCreate(const int n,tree t[])
建树：
输入n个结点的值，如果为空置为-1。
int FindRoot(const int n,tree t[])
寻找根节点：
记录左右结点的值到一个数组中，以他们的值为下标，并且数组初始化为0，如果没有被置为1，即还是0的话，说明它是根结点。最后返回根结点的下标。
int FindLeaves(const int n,int queue[],tree t[],int root,int leaves[])
寻找叶子节点：
首先初始化队列，队头队尾指针均置为0；
如果只有一个结点的话，那么叶子节点就为root根结点。返回根结点。
将根结点置为队列的第一个元素。
尾指针++；
用cnt来计数，共判断n个结点是否为叶子节点：
左子树为根结点的左节点，右子树为根结点的右节点。
如果左右节点都为空，那么是叶子节点。
如果一个为空，另一个不为空，那么将不为空的入队，作为根节点。尾指针++
如果都不为空，那么按照左右顺序入队。
void Output(const int cnt,int leaves[])
格式化输出：
结尾不能有多余空格。

主函数
根结点置为-1，输入节点的个数。定义一个tree并初始化，寻找根结点，开辟两个数组分别用来存根结点和叶子节点，记录叶子节点的个数，输出叶子节点。

AC代码：

#include<bits/stdc++.h>
using namespace std;

typedef int idx;

typedef struct node{
    idx left;
    idx right;
}tree;

void TreeCreate(const int n,tree t[]);
idx FindRoot(const int n,tree t[]);
int FindLeaves(const int n,idx queue[],tree t[],idx root,idx leaves[]);
void Output(const int cnt,idx leaves[]);

void TreeCreate(const int n,tree t[])
{
    char left,right;
    for(int i=0;i<n;i++)
    {
        cin>>left>>right;
        if(left=='-') t[i].left=left=-1;
        else t[i].left=left-'0';
        if(right=='-') t[i].right=-1;
        else t[i].right=right-'0';
    }
}

idx FindRoot(const int n,tree t[])
{
    int a[n];
    for(int i=0;i<n;i++) a[i]=0;
    for(int i=0;i<n;i++)
    {
        if(t[i].left!=-1){
            a[t[i].left]=1;
        }
        if(t[i].right!=-1)
        {
            a[t[i].right]=1;
        }
    }
    for(idx i=0;i<n;i++)
    {
        if(a[i]==0) return i;
    }
    return 0;
}
int FindRoot(const int n,idx queue[],tree t[],idx root, idx leaves[])
{
    int qhead=0,qtail=0;//初始化队列头尾指针，此时队列为空
    if(n==1){
        leaves[0]=root;
        return 1;
    }
    queue[qhead]=root;
    qtail=1;
    int cnt=0;
    for(int i=0;i<n;i++){
        //共判断n个结点，一共n次
        idx leftTree =t[queue[qhead]].left;
        idx rightTree=t[queue[qhead]].right;
        if(leftTree==-1&&rightTree==-1){
            leaves[cnt++]=queue[qhead];
            qhead++;
            qhead%=n;
        }
        else if(leftTree!=-1&&rightTree==-1){
            queue[qtail++]=leftTree;
            qhead++;
            qhead%=n;
        }
        else if(leftTree==-1&&rightTree!=-1){
            queue[qtail++]=rightTree;
            qhead++;
            qhead%=n;
        }
        else if(leftTree!=-1&&rightTree!=-1){
            queue[qtail++]=leftTree;
            queue[qtail++]=rightTree;
            qhead++;
            qhead%=n;
        }
    }
    return cnt;
}

void Output(const int cnt,idx leaves[])
{
    for(int i=0;i<cnt-1;i++) cout<<leaves[i]<<" ";
    cout<<leaves[cnt-1];
}

int main()
{
    idx root=-1;
    int n;
    cin>>n;
    tree t[n];
    TreeCreate(n,t);
    root=FindRoot(n,t);
    idx queue[n];
    idx leaves[n];
    int cnt=FindRoot(n,queue,t,root,leaves);//返回叶节点数量，并存在found里。
    Output(cnt,leaves);
    return 0;
}