关于算法-数据结构:PAT甲级1102-Invert-a-Binary-Tree

题目粗心：

给定一个二叉树(编号从0到N-1),和每个结点的左右孩子编号,把该二叉树进行反转,而后输入反转二叉树的层序遍历和中序遍历

算法思路：

这个题目有两种办法能够求解,一是依照题目要求间接将二叉树进行反转取得新的二叉树,而后再遍历。第二种就是不扭转二叉树,作镜像遍历,也即是之前先遍历左孩子,当初变成先遍历右孩子,毕竟只须要输入遍历的后果,就无需进行二叉树的反转,这里抉择用第二种,当然了,如果想要反转的话,间接应用后序遍历的办法,在最初拜访根节点的操作变动为替换其左右孩子节点即可($swap$函数就能够实现)。

取得根节点的办法：

这里应用了一个标记数组$isNotRoot$标记下标为i的节点是否为根节点，不是就是$true$,初始默认都是根节点，在每输出一行数据的时候，就阐明以后的输出节点为其余节点的孩子节点，肯定不是根节点，就将$isNotRoot$置为$true$，而后在输出结束后，遍历$isNotRoot$查找为$false$的下标$i$即为$root$。(实际上是双亲表示法)

提交后果：

AC代码：

#include <cstdio>
#include <string>
#include <iostream>
#include <queue>

using namespace std;

struct Node{
    int data,left,right;
};

int N;// 节点个数
int root;// 根节点编号
bool isNotRoot[20];// 判断节点是否为根节点，不是就是true。
Node tree[20];

void levelTravese(){
    queue<int> q;
    q.push(root);
    int num = 0;
    while (!q.empty()){
        int top = q.front();
        q.pop();
        printf("%d",top);
        if(num<N-1) printf(" ");
        ++num;
        if(tree[top].right!=-1){
            q.push(tree[top].right);
        }
        if(tree[top].left!=-1){
            q.push(tree[top].left);
        }
    }
}

int num = 0;
void inOrder(int r){
    if(r==-1) return;
    inOrder(tree[r].right);
    printf("%d",r);
    if(num<N-1) printf(" ");
    ++num;
    inOrder(tree[r].left);
}

int main()
{
    scanf("%d",&N);
    string s1,s2;
    for (int i = 0; i < N; ++i) {
        cin>>s1>>s2;
        int left,right;
        tree[i].data = i;
        if(s1!="-"){
            // 是数字
            left = stoi(s1);
            isNotRoot[left] = true;// 为左孩子节点，肯定不是根节点
            tree[i].left = left;
        } else {
            tree[i].left = -1;
        }
        if(s2!="-"){
            // 是数字
            right = stoi(s2);
            isNotRoot[right] = true;// 为左孩子节点，肯定不是根节点
            tree[i].right = right;
        } else {
            tree[i].right = -1;
        }
    }
    // 找到根节点
    for (int j = 0; j < N; ++j) {
        if(!isNotRoot[j]){
            root = j;
            break;
        }
    }
    levelTravese();
    printf("\n");
    inOrder(root);
    return 0;
}