本文主要是介绍个人练习-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;
}
这篇关于个人练习-PAT甲级-1099 Build A Binary Search Tree的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!