5.7阿里笔试第二题

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;

class MyNode
{
public:
	int val;
	MyNode* pre;
	MyNode* left;
	MyNode* right;
	int deep;

	MyNode(int v, MyNode* p, MyNode* l, MyNode* r, int d) :val(v), pre(p), left(l), right(r), deep(d)
	{
		//cout << val << "," << deep << ",";
		//if (pre == NULL)cout << "null" << ",";
		//else cout << pre->val << ",";
		//if (left == NULL)cout << "null" << ",";
		//else cout << left->val << ",";
		//if (right == NULL)cout << "null" << ",";
		//else cout << right->val << ",";
		//cout << endl;
	}
	static bool cmp(MyNode* a, MyNode* b) {
		if (a->deep < b->deep)return true;
		if (a->deep > b->deep)return false;
		return a->val < b->val;
	}
};

int main()
{
	int n, k;
	cin >> n >> k;

	vector<int> arr(n, 0);
	for (int i = 0; i<n; ++i)
	{
		cin >> arr[i];
	}
	if (n <= 2)
	{
		for (int i = 0; i + 1<n; ++i)
		{
			cout << arr[i] << " ";
		}
		cout << arr.back();
		return 0;
	}

	MyNode* root = new MyNode(arr[0], NULL,NULL, NULL,1);
	vector<MyNode*> tree;
	tree.push_back(root);
	for (int i = 1; i < n; ++i)
	{
		MyNode* cur = root;
		while (true)
		{
			if (arr[i] < cur->val)
			{
				if (cur->left == NULL)
				{
					MyNode* newn = new MyNode(arr[i], cur, NULL, NULL,cur->deep+1);
					tree.push_back(newn);
					cur->left = newn;
					break;
				}
				else
				{
					cur = cur->left;
				}
			}
			else if (arr[i] >= cur->val)
			{
				if (cur->right == NULL)
				{
					MyNode* newn = new MyNode(arr[i], cur, NULL, NULL, cur->deep + 1);
					tree.push_back(newn);
					cur->right = newn;
					break;
				}
				else
				{
					cur = cur->right;
				}
			}

		}

	}

	sort(tree.begin(), tree.end(), MyNode::cmp);
	vector<int> tmp;
	int pred = 1;
	for (int i = 0; i<n; ++i)
	{
		if (tree[i]->deep != pred)
		{
			for (int j = 0; j < tmp.size(); ++j)
			{
				cout << tmp[(j - k + tmp.size()) % tmp.size()] << " ";
			}
			tmp.clear();
			pred = tree[i]->deep;
		}
		tmp.push_back(tree[i]->val);
	}
	for (int j = 0; j < tmp.size(); ++j)
	{
		cout << tmp[(j - k + tmp.size()) % tmp.size()] << " ";
	}
	return 0;
}