个人练习-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;
}