关于算法-数据结构: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;
}