【LeetCode & 剑指offer刷题】熟悉OJ平台3：OJ编程实例

【LeetCode & 剑指offer 刷题笔记】目录（持续更新中...）

OJ编程实例

给定一棵二叉树的前序（根、左、右）和中序（左、根、右）的打印结果，输出此二叉树按层（从左往右）打印结果。

例如一棵二叉树前序：1 2 4 5 3；中序：4 2 5 1 3。可以构建出下图所示二叉树：

按层打印的结果则为：1 2 3 4 5。

按层打印二叉树（去哪儿网2017春招真题）

题目描述

输入第一行只有一个数字，表示二叉树的节点数n（1<=n<=1000）; 第二行由a1,a2,...,an(1<=ai<=1000)组成的整数序列（用空格分隔）—表示前序打印结果；第三行由b1,b2,...,bn(1<=bi<=1000)组成的整数序列（用空格分隔）—表示中序打印结果。	样例输入 5 1 2 4 5 3 4 2 5 1 3
输出 c1,c2,...,cn，用空格分隔—表示按层打印的结果。	样例输出 1 2 3 4 5
时间限制 C/C++语言：2000MS 其它语言：4000MS	内存限制 C/C++语言：65536KB 其它语言：589824KB

using namespace std;
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) :val(x), left(NULL), right(NULL) {} //参数初始化列表
};
using iter = vector<int>::iterator;
TreeNode* createTree(iter prebegin, iter preend, iter inbegin, iter inend);
void levelOrder(TreeNode* root);
int main()
{
/*  if (freopen("./src/input.txt", "r", stdin))//代替手工输入,需加<cstdio>头文件,vs默认路径起点为工程文件所在的目录
        cout << "读取成功" << endl;
    else
        cout << "读取文件失败" << endl;*/
    int n;
    cin >> n;
    vector<int> preorder(n);
    vector<int> inorder(n);
    for (int i = 0; i<n; i++)
    {
        cin >> preorder[i];
    }
    for (int i = 0; i<n; i++)
    {
        cin >> inorder[i];
    }
    TreeNode* root = createTree(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
    levelOrder(root);
    return 0;
}
TreeNode* createTree(iter prebegin, iter preend, iter inbegin, iter inend)
{
    if (prebegin >= preend || inbegin >= inend) return nullptr;
    TreeNode* root = new TreeNode(*prebegin);
    iter root_pos = find(inbegin, inend, root->val);
    int left_length = root_pos - inbegin;
    root->left = createTree(prebegin + 1, prebegin + left_length + 1, inbegin, root_pos);
    root->right = createTree(prebegin + left_length + 1, preend, root_pos + 1, inend);
    return root;
}
void levelOrder(TreeNode* root)
{
    if (root == nullptr) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty())
    {
        int size = q.size();
        for (int i = 0; i<size; i++)
        {
            TreeNode* node = q.front();
            cout << node->val << ' ';
            q.pop();
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
}

集合（京东2017秋招真题）

题目描述

给你两个集合，要求 {A} + {B}。

注：同一个集合中不会有两个相同的元素。

输入多组（不超过 5 组）数据。每组输入数据分为三行，第一行有两个数字 n,m($0＜n,mleq10000$)，分别表示集合 A 和集合 B 的元素个数。后两行分别表示集合 A 和集合 B。每个元素为不超出 int 范围的整数，每个元素之间有一个空格隔开。	样例输入 1 2 1 2 3 1 2 1 1 2
输出针对每组数据输出一行数据，表示合并后的集合，要求从小到大输出，每个元素之间有一个空格隔开。	样例输出 1 2 3 1 2
时间限制 C/C++语言：1000MS 其它语言：3000MS	内存限制 C/C++语言：65536KB 其它语言：589824KB

#include<iostream>
#include<set>
using namespace std;
int main()
{
  int m,n;
  while(cin>>m>>n) //不确定会输入多少组
  {
      set<int> s;
      int t;
      for(int i=0;i<m;++i)
      {
        cin>>t;
        s.insert(t);
      }
      for(int i=0;i<n;++i)
      {
        cin>>t;
        s.insert(t);
      }
     for(set<int>::iterator it=s.begin();it!=s.end();it++)
      {
          cout<<*it<<" "; //按从小到大输出
      }
      cout<<endl;
  }
 
  return 0;
}

题目来源：http://exercise.acmcoder.com/online/online_judge_ques?ques_id=4172&konwledgeId=169