1064. Complete Binary Search Tree

题目大意

给定一个序列, 求其生成Complete BST 的层序遍历.

思路

最开始把这个题想复杂了, 还想着建立结构体, 其实用数组最为方便简单

中序遍历这棵 Complete BST, 依次填入一个排好序的序列.
因为是数组存放, 所以直接输出 1 - nNode 就好.

代码

#include <iostream>

#include <cstdio>

#include <vector>

#include <algorithm>

#define MAXN 2000

using namespace std;

int nNode;

int curSeq = 0;

vector<int> seq;

int arr[MAXN];

void dfs(int root){

    if(root > nNode)

        return;

    dfs(root << 1);

    arr[root] = seq[curSeq++];

    dfs(root << 1 | 1);

}

int main(){

    scanf("%d", &nNode);

    seq.resize(nNode);

    for(int i = 0; i < nNode; i++)

        scanf("%d", &seq[i]);

    sort(seq.begin(), seq.end());

    dfs(1);

    for(int i = 1; i <= nNode; i++){

        if(i != 1) printf(" ");

        printf("%d", arr[i]);

    }

    return 0;

}

巴特西

PAT1064. Complete Binary Search Tree

1064. Complete Binary Search Tree

题目大意

思路

代码

最新文章

热门文章