首页 > 代码库 > 1156. Binary tree 二叉树找根方法

1156. Binary tree 二叉树找根方法

2024-11-03 09:15:02   209人阅读

#include "iostream"
#include "memory.h"
using namespace std;


/*
找根方法：
每个节点输入次数：根节点在输入自己时输入一次，
非根节点在输入父节点时输入一次，在输入自己时又输入
一次，所以输入了两次。所以可以通过计数器，计算每个节点
被输入的次数来找出根节点。
*/
const int MAX = 1002;
struct Node{
int id;
char val;
int left, right;
Node(char c, int i = 0){
id = i;
val = c;
left = 0;
right = 0;
}
Node(){
left = 0;
right = 0;
}
};


void preOrder(int root, Node *node){
if (root != 0){
cout << node[root].val;
preOrder(node[root].left, node);
preOrder(node[root].right, node);
}
}
int main(){
int n;
while (cin >> n){
int isroot[MAX];
Node node[MAX];
memset(isroot, 0, sizeof(isroot));
int id, left, right;
char value;
for (int i = 0; i < n; i++){
cin >> id >> value >> left >> right;
node[id].id = id;
node[id].val = value;
node[id].left = left;
node[id].right = right;
isroot[id]++;
isroot[left]++;
isroot[right]++;
}
int root;
for (int i = 0; i < MAX; i++){
if (isroot[i] % 2 == 1){ //输入次数为次数的节点为根
root = i;
}
}
preOrder(root, node);
cout << endl;
}
return 0;
}

1156. Binary tree 二叉树找根方法


联系
我们