You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
110 lines
2.2 KiB
110 lines
2.2 KiB
2 years ago
|
#include <iostream>
|
||
|
#include <cstddef>
|
||
|
#include <deque>
|
||
|
|
||
|
class Node {
|
||
|
public:
|
||
|
int data;
|
||
|
Node *left;
|
||
|
Node *right;
|
||
|
Node(int d) {
|
||
|
data = d;
|
||
|
left = NULL;
|
||
|
right = NULL;
|
||
|
}
|
||
|
};
|
||
|
|
||
|
class Solution {
|
||
|
public:
|
||
|
Node* insert(Node* root, int data) {
|
||
|
if(root == NULL) {
|
||
|
return new Node(data);
|
||
|
} else {
|
||
|
Node* cur;
|
||
|
if(data <= root->data) {
|
||
|
cur = insert(root->left, data);
|
||
|
root->left = cur;
|
||
|
} else {
|
||
|
cur = insert(root->right, data);
|
||
|
root->right = cur;
|
||
|
}
|
||
|
|
||
|
return root;
|
||
|
}
|
||
|
}
|
||
|
|
||
|
/* you only have to complete the function given below.
|
||
|
Node is defined as
|
||
|
|
||
|
class Node {
|
||
|
public:
|
||
|
int data;
|
||
|
Node *left;
|
||
|
Node *right;
|
||
|
Node(int d) {
|
||
|
data = d;
|
||
|
left = NULL;
|
||
|
right = NULL;
|
||
|
}
|
||
|
};
|
||
|
|
||
|
*/
|
||
|
|
||
|
// void preOrder(Node *root) {
|
||
|
// /* #include <deque> */
|
||
|
// std::deque<Node*> q {root};
|
||
|
//
|
||
|
// while (!q.empty()) {
|
||
|
// auto elem = q.back();
|
||
|
//
|
||
|
// q.pop_back();
|
||
|
//
|
||
|
// while (elem != nullptr) {
|
||
|
// if (elem->right != nullptr) {
|
||
|
// q.push_back(elem->right);
|
||
|
// }
|
||
|
//
|
||
|
// std::cout << elem->data << " ";
|
||
|
//
|
||
|
// elem = elem->left;
|
||
|
// }
|
||
|
// }
|
||
|
// }
|
||
|
|
||
|
void printLeft(Node *left, Node *right) {
|
||
|
|
||
|
while (left != nullptr) {
|
||
|
std::cout << " " << left->data;
|
||
|
|
||
|
if (left->right != nullptr) {
|
||
|
printLeft(left->left, left->right);
|
||
|
break;
|
||
|
}
|
||
|
|
||
|
left = left->left;
|
||
|
}
|
||
|
|
||
|
if (right != nullptr) {
|
||
|
std::cout << " " << right->data;
|
||
|
|
||
|
printLeft(right->left, right->right);
|
||
|
}
|
||
|
}
|
||
|
|
||
|
void preOrder(Node *root) {
|
||
|
if (root == nullptr) {
|
||
|
return;
|
||
|
}
|
||
|
|
||
|
std::cout << root->data;
|
||
|
|
||
|
printLeft(root->left, root->right);
|
||
|
}
|
||
|
|
||
|
}; //End of Solution
|
||
|
|
||
|
int main() {
|
||
|
std::cout << "Hello, World!" << std::endl;
|
||
|
return 0;
|
||
|
}
|