[数据结构与算法]个人练习-PAT甲级-1099 Build A Binary Search Tree

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805367987355648

题目大意：给出一颗BST的结构，以及一串数字，可以得到唯一的二叉搜索树。求这棵BST的层序遍历。

复习了下中序遍历和层序遍历。因为BST的中序遍历结果就是从小到大排序，所以首先可以将这串数字arr[]排序（即得到中序遍历的结果），然后对树进行中序遍历，依次插入arr[]的元素的值。注意如果子节点为空那么跳过即可。cnt记录下一个要被插入树中的arr[]元素的下标。

void inOrder(int idx) {
    if (tree[idx].left_idx != -1)
        inOrder(tree[idx].left_idx);
    tree[idx].val = arr[cnt++];
    if (tree[idx].right_idx != -1)
        inOrder(tree[idx].right_idx);
}

层序遍历，要用到一个队列。每次pop()队首元素前，先把其所有子节点都从左到右push()进队列，然后将队首元素pop()并输出。注意此时cnt的含义变为【已经pop()了多少个结果】，在第二个及以后的输出时要加一个空格。

void levelOrider() {
    q.push(tree[0]);
    while (q.empty() == false) {
        if (q.front().left_idx != -1)
            q.push(tree[q.front().left_idx]);
        if (q.front().right_idx != -1)
            q.push(tree[q.front().right_idx]);
        if (cnt == 0) {
            printf("%d", q.front().val);
            cnt++;
        }
        else {
            printf(" %d", q.front().val);
        }
        q.pop();
    }
}

总结：主要还是树的遍历要记牢。

完整代码

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;


class Node {
public:
    int val;
    int left_idx, right_idx;
};

vector<int> arr;
vector<Node> tree;
queue<Node> q;
int cnt;


void inOrder(int idx) {
    if (tree[idx].left_idx != -1)
        inOrder(tree[idx].left_idx);
    tree[idx].val = arr[cnt++];
    if (tree[idx].right_idx != -1)
        inOrder(tree[idx].right_idx);
}


void levelOrider() {
    q.push(tree[0]);
    while (q.empty() == false) {
        if (q.front().left_idx != -1)
            q.push(tree[q.front().left_idx]);
        if (q.front().right_idx != -1)
            q.push(tree[q.front().right_idx]);
        if (cnt == 0) {
            printf("%d", q.front().val);
            cnt++;
        }
        else {
            printf(" %d", q.front().val);
        }
        q.pop();
    }
}


int main() {
    int N;
    scanf("%d", &N);
    tree.resize(N);
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &tree[i].left_idx, &tree[i].right_idx);
    }
    arr.resize(N);
    for (int i = 0; i < N; i++)
        scanf("%d", &arr[i]);

    sort(arr.begin(), arr.end());
    inOrder(0);
    cnt = 0;
    levelOrider();


    return 0;
}