AcWing 3595. 二叉排序树【非递归版本,考察基本功】
原题链接
简单
作者:
FrankieNCU
,
2023-05-08 21:11:37
,
所有人可见
,
阅读 279
数据结构
#include <cstdio>
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int _val): val(_val), left(NULL), right(NULL) {}
};
int main() {
int n, t;
TreeNode* root = new TreeNode(-1);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> t;
TreeNode* r = new TreeNode(t);
if ( root -> val == -1 ) root -> val = t, puts("-1");
else {
int father;
TreeNode* temp = root;
while ( temp ) {
if ( temp -> val > r -> val ) {
father = temp -> val;
if ( !temp -> left ) temp -> left = r, temp = NULL;
else temp = temp -> left;
}
else if ( temp -> val < r -> val ) {
father = temp -> val;
if ( !temp -> right ) temp -> right = r, temp = NULL;
else temp = temp -> right;
}
}
printf("%d\n", father);
}
}
return 0;
}