(PAT 1102) Invert a Binary Tree(反转二叉树+寻找二叉树的根结点)-蒲公英云

(PAT 1102) Invert a Binary Tree(反转二叉树+寻找二叉树的根结点)

冷不防 2022-04-23 03:54 229阅读 0赞

The following is from Max Howell @twitter:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can't invert a binary tree on a whiteboard so fuck off.

Now it’s your turn to prove that YOU CAN invert a binary tree!

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 from 0 to N−1, 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 the first line the level-order, and then in the second line the in-order traversal sequences of the inverted tree. 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:

3 7 2 6 4 0 5 1
6 5 7 4 3 2 0 1

解题思路:

利用前序遍历,遍历到每一个结点时,交换该结点的左右子树即可

void invertBinaryTree(int root) {
    if (root == -1) return;
    swap(BTree[root].lchild, BTree[root].rchild);
    invertBinaryTree(BTree[root].lchild);
    invertBinaryTree(BTree[root].rchild);
}

这里的坑点是怎样寻找二叉树的根结点: 根据性质,二叉树根节点是只有出度没有入度的,所以在插入节点时,给每个子节点上一个不是根节点的标记,最后没有被上标记的那个就是根节点

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 100001;
int N;
struct sNode {
    int lchild = -1, rchild = -1;
    bool notRoot = false;
}BTree[MAXN];
void invertBinaryTree(int root) {
    if (root == -1) return;
    swap(BTree[root].lchild, BTree[root].rchild);
    invertBinaryTree(BTree[root].lchild);
    invertBinaryTree(BTree[root].rchild);
}
int num1 = 0;
void inorder(int root) {
    if (BTree[root].lchild != -1) {
        inorder(BTree[root].lchild);
    }
    cout << root;
    num1++;
    if (num1 < N) cout << " ";
    if (BTree[root].rchild != -1) {
        inorder(BTree[root].rchild);
    }
}
int num2 = 0;
void LayerOrder(int root) {
    queue<int> BFS_QUeue;
    BFS_QUeue.push(root);
    while (!BFS_QUeue.empty()) {
        cout << BFS_QUeue.front();
        int curnode = BFS_QUeue.front();
        num2++;
        if (num2 < N) cout << " ";
        BFS_QUeue.pop();
        if (BTree[curnode].lchild != -1) {
            BFS_QUeue.push(BTree[curnode].lchild);
        }
        if (BTree[curnode].rchild != -1) {
            BFS_QUeue.push(BTree[curnode].rchild);
        }
    }
}
int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        char lc, rc;
        scanf("%*c%c %c", &lc, &rc);
        if (lc == '-' && rc == '-') {
            BTree[i].lchild = -1;
            BTree[i].rchild = -1;
            BTree[BTree[i].lchild].notRoot = true;
            BTree[BTree[i].rchild].notRoot = true;
        }
        else if (lc == '-' || rc == '-') {
            if (lc == '-') {
                BTree[i].lchild = -1;
                BTree[i].rchild = rc - '0';
                BTree[BTree[i].rchild].notRoot = true;
            }
            else if(rc == '-'){
                BTree[i].lchild = lc - '0';
                BTree[i].rchild = -1;
                BTree[BTree[i].lchild].notRoot = true;
            }
        }
        else {
            BTree[i].lchild = lc - '0';
            BTree[i].rchild = rc - '0';
            BTree[BTree[i].lchild].notRoot = true;
            BTree[BTree[i].rchild].notRoot = true;
        }
    }
    //确立根结点
    int droot = 0;
    for (int i = 0; i < N; ++i) {
        if (BTree[i].notRoot == false) {
            droot = i;
            break;
        }
    }
    //反转二叉树
    invertBinaryTree(droot);
    LayerOrder(droot);
    cout << endl;
    inorder(droot);
    system("PAUSE");
    return 0;
}