fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. class node
  8. {
  9. public:
  10. 	node()
  11. 	{
  12. 		id =0;
  13. 		Lchild = nullptr;
  14. 		Mchild = nullptr;
  15. 		Rchild = nullptr;
  16. 	}
  17. 	node(int id)
  18. 	{
  19. 		this->id = id;
  20. 		Lchild = nullptr;
  21. 		Mchild = nullptr;
  22. 		Rchild = nullptr;
  23. 	}
  24. 	int id;
  25. 	node* Lchild;
  26. 	node* Mchild;
  27. 	node* Rchild;
  28. };
  29.  
  30. node* build(vector<int> preOrder, vector<int> inOrder, int start, int end);
  31. void findIndex(int id, vector<int> inOrder, int strat, int end, int &pos1, int &pos2);
  32. void postOrder(node* root);
  33.  
  34.  
  35. int main()
  36. {
  37. 	ios_base::sync_with_stdio(false);
  38. 	std::cin.tie(nullptr);
  39. 	int n;
  40. 	cin >> n;
  41. 	vector<int> preOrder, inOrder;
  42. 	preOrder.resize(n);
  43. 	inOrder.resize(n * 2);
  44. 	for (int i = 0;i < n;i++)
  45. 	{
  46. 		int num;
  47. 		cin >> num;
  48. 		preOrder[i] = num;
  49. 	}
  50. 	for (int i = 0;i < n * 2;i++)
  51. 	{
  52. 		int num;
  53. 		cin >> num;
  54. 		inOrder[i] = num;
  55. 	}
  56.  
  57. 	node* root = build(preOrder, inOrder, 0, n * 2 - 1);
  58. 	postOrder(root);
  59.  
  60. 	system("pause");
  61. 	return 0;
  62. }
  63.  
  64. node* build(vector<int> preOrder, vector<int> inOrder, int start, int end)
  65. {
  66. 	static int preOrder_index = 0;
  67. 	if (preOrder_index == preOrder.size())
  68. 		return nullptr;
  69.  
  70. 	if (start >= end)
  71. 		return nullptr;
  72.  
  73. 	node* r = new node(preOrder[preOrder_index]);
  74. 	preOrder_index++;
  75. 	if (start == end - 1)
  76. 		return r;
  77.  
  78. 	int pos1 = -1, pos2 = -1;
  79. 	findIndex(r->id, inOrder, start, end, pos1, pos2);
  80.  
  81. 	r->Lchild = build(preOrder, inOrder, start, pos1 - 1);
  82. 	r->Mchild = build(preOrder, inOrder, pos1 + 1, pos2 - 1);
  83. 	r->Rchild = build(preOrder, inOrder, pos2 + 1, end);
  84.  
  85. 	return r;
  86. }
  87.  
  88. void findIndex(int id, vector<int> inOrder, int start, int end, int &pos1, int &pos2)
  89. {
  90. 	for (int i = start;i <= end;i++)
  91. 	{
  92. 		if (id == inOrder[i])
  93. 		{
  94. 			if (pos1 == -1)
  95. 			{
  96. 				pos1 = i;
  97. 				continue;
  98. 			}
  99. 			else
  100. 			{
  101. 				pos2 = i;
  102. 				break;
  103. 			}
  104. 		}
  105. 	}
  106. }
  107.  
  108. void postOrder(node* root)
  109. {
  110. 	if (root != nullptr)
  111. 	{
  112. 		postOrder(root->Lchild);
  113. 		postOrder(root->Mchild);
  114. 		postOrder(root->Rchild);
  115. 		cout << root->id << " ";
  116.  
  117. 	}
  118. }
Success #stdin #stdout #stderr 0s 4412KB
comments (?)
stdin
copy 
15
1 2 5 9 10 11 6 3 7 12 4 8 13 14 15
9 9 5 10 10 5 11 11 2 6 6 2 1 7 7 12 12 3 3 1 4 4 13 13 8 14 14 8 15 15
stdout
copy 
9 10 11 5 6 2 12 7 3 13 14 15 8 4 1
stderr
copy 
sh: 1: pause: not found
https://ideone.com/4Pjvqx
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!