🎈 原创

反转二叉树，虽然不是BST但也是树相关的题目，就也写一下吧。

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.

反转二叉树不需要想的太复杂，可以在对一棵树的后序遍历中将树的左右子树进行交换。前序也可以，但是交换后会使遍历的顺序变成先右后左，不过对最终的结果是没有影响的。

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

#include <iostream>
#include <queue>
using namespace std;

struct Node
{
    int left;
    int right;
}node[11];
int N;
int count = 0;

int getNode(void);
void LevelTraverse(int root);
void InOrderTraverse(int root);

int main(int argc, const char *argv[])
{
    int root = getNode();
    LevelTraverse(root);
    cout << endl;
    InOrderTraverse(root);
    cout << endl;

    return 0;
}

int getNode(void)
{
    cin >> N;
    bool hashTable[N] = {false};
    for(int i = 0; i < N; i++)
    {
        char l, r;
        getchar();
        scanf("%c %c", &l, &r);
        if(l == '-')
            node[i].right = -1;
        else
        {
            node[i].right = l - '0';
            hashTable[l - '0'] = true;
        }
        if(r == '-')
            node[i].left = -1;
        else
        {
            node[i].left = r - '0';
            hashTable[r - '0'] = true;
        }
    }
    for(int i = 0; i < N; i++)
        if(hashTable[i] == false)
            return i;
    return -1;
}

void LevelTraverse(int root)
{
    int cnt = 0;
    queue<int> Q;
    if(root != -1)
        Q.push(root);
    while(!Q.empty())
    {
        int tmp = Q.front();
        Q.pop();
        cout << tmp;
        cnt++;
        if(cnt < N)
            cout << " ";
        if(node[tmp].left != -1)
            Q.push(node[tmp].left);
        if(node[tmp].right != -1)
            Q.push(node[tmp].right);
    }
}

void InOrderTraverse(int root)
{
    if(root != -1)
    {
        InOrderTraverse(node[root].left);
        cout << root;
        count++;
        if(count < N)
            cout << " ";
        InOrderTraverse(node[root].right);
    }
}

---

BST的一个特性就是对这棵树中序遍历时的序列是从小到大的有序列，可以利用这一特性将一个有序的数列填入到一颗BST中。

1064 Complete Binary Search Tree (30 point(s))

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
• Both the left and right subtrees must also be binary search trees.

A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.

Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤1000). Then N distinct non-negative integer keys are given in the next line. All the numbers in a line are separated by a space and are no greater than 2000.

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input:

10
1 2 3 4 5 6 7 8 9 0

Sample Output:

6 3 8 1 5 7 9 0 2 4

#include <iostream>
#include <algorithm>
using namespace std;

int cnt = 0;
void InOrder(int root, int num[], int CBT[], int N);

int main(int argc, const char *argv[])
{
    int N;
    cin >> N;
    int num[N], CBT[N + 1];
    for(int i = 0; i < N; i++)
        cin >> num[i];
    sort(num, num + N);
    InOrder(1, num, CBT, N);
    for(int i = 1; i <= N; i++)
    {
        cout << CBT[i];
        if(i < N)
            cout << " ";
    }
    cout << endl;

    return 0;
}

void InOrder(int root, int num[], int CBT[], int N)
{
    if(root > N)
        return;
    else
    {
        InOrder(root * 2, num, CBT, N);
        CBT[root] = num[cnt++];
        InOrder(root * 2 + 1, num, CBT, N);
    }
}

1099 Build A Binary Search Tree (30 point(s))

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
• Both the left and right subtrees must also be binary search trees.

Given the structure of a binary tree and a sequence of distinct integer keys, there is only one way to fill these keys into the tree so that the resulting tree satisfies the definition of a BST. You are supposed to output the level order traversal sequence of that tree. The sample is illustrated by Figure 1 and 2.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤100) which is the total number of nodes in the tree. The next N lines each contains the left and the right children of a node in the format left_index right_index, provided that the nodes are numbered from 0 to N−1, and 0 is always the root. If one child is missing, then −1 will represent the NULL child pointer. Finally N distinct integer keys are given in the last line.

Output Specification:

For each test case, print in one line the level order traversal sequence of that tree. All the numbers must be separated by a space, with no extra space at the end of the line.

Sample Input:

9
1 6
2 3
-1 -1
-1 4
5 -1
-1 -1
7 -1
-1 8
-1 -1
73 45 11 58 82 25 67 38 42

Sample Output:

58 25 82 11 38 67 45 73 42

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct node
{
    int data;
    int left, right;
};
int N;
int cnt = 0, n = 0;
void InOrder(int root, node Tree[], int num[]);
void BFS(node Tree[], int root);

int main(int argc, const char *atgv[])
{
    cin >> N;
    node Tree[N];
    for(int i = 0; i < N; i++)
        cin >> Tree[i].left >> Tree[i].right;
    int num[N];
    for(int i = 0; i < N; i++)
        cin >> num[i];
    sort(num, num + N);
    InOrder(0, Tree, num);
    BFS(Tree, 0);

    return 0;
}

void InOrder(int root, node Tree[], int num[])
{
    if(root == -1)
        return;
    else
    {
        InOrder(Tree[root].left, Tree, num);
        Tree[root].data = num[cnt++];
        InOrder(Tree[root].right, Tree, num);
    }
}

void BFS(node Tree[], int root)
{
    queue<int> Q;
    if(root != -1)
        Q.push(root);
    while(!Q.empty())
    {
        int tmp = Q.front();
        Q.pop();
        cout << Tree[tmp].data;
        n++;
        if(n < N)
            cout << " ";
        if(Tree[tmp].left != -1)
            Q.push(Tree[tmp].left);
        if(Tree[tmp].right != -1)
            Q.push(Tree[tmp].right);
    }
}