描述

Given an array A1, A2, … AN, your task is to build a binary treee T which satisfies the following requirments:

  1. T is a min-heap;

  2. The inorder traversal sequence of T is A1, A2, … AN.

    For example if the array is 3, 2, 8, 1, 4, 7, the tree is as below: 

    1
    2
    3
    4
    5
        1
       / \
      2   4
     / \   \
    3   8   7

输入

The first line contain an integer N denoting the array length. (1 <= N <= 100)

The second line contains N distinct integers denoting A1, A2, … AN. (1 <= Ai <= 1000000)

输出

Output the preorder traversal sequence of T.

样例输入

6
3 2 8 1 4 7

样例输出

1 2 3 8 4 7

《Building Heap》题目分析

这道题是一道比较简单的递归题目。大家一定都做过这样一道经典的题目：“已知一棵二叉树的中序和后序遍历，求先序遍历。”

这道题也是类似，堆的性质可以让我们确定最小的元素一定是根，比如在样例中1一定是根。

然后根据中序遍历的顺序，1左边的一定是左子树部分，1右边的一定是右子树的部分。

左右子树都可以递归求解。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

void min_between(int a[], int l, int r)
{
    if(l > r) return;
    int tag = l;
    for(int i = l; i <= r; i++) {
        if(a[i] < a[tag]) tag = i;
    }
    cout << a[tag] << ' ';   //先序遍历，先根部
    min_between(a, l, tag - 1); //左子树
    min_between(a, tag + 1, r); //右子树
    return;
}

int main()
{
    int N, a[105];
    cin >> N;
    for(int i = 0; i < N; i++) cin >> a[i];
    min_between(a, 0, N - 1);
    return 0;
}