首页 > 代码库 > 1156. Binary tree 二叉树找根方法
1156. Binary tree 二叉树找根方法
#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;
}
#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 二叉树找根方法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。