이진트리 #Traverse #DFS

이제 20%대 문제도 왠만하면 잘 풀리는 것 같다.

조금 더 열심히 해서 20%대 문제 수월하게 풀 수 있게 되면 10%대 문제들도 많이 도전해 봐야겠다.

이진트리

한 노드가 최대 2개의 자식 노드를 가지는 트리

이진트리 탐색(Binary Tree Traverse)

in-order : 왼쪽 자식노드, 내 노드, 오른쪽 자식노드 순서로 방문한다.

pre-order : 내 노드, 왼쪽 자식노드, 오른쪽 자식노드 순서로 방문한다.

post-order : 왼쪽 자식노드, 오른쪽 자식노드, 내 노드 순서로 방문한다.

level-order : 내 노드, 내 노드로부터 깊이 1인 노드들, 내 노드로부터 깊이 2인 노드들, ... , 내 노드로부터 깊이 N인 노드들 (N: 나(트리)의 깊이)

#트리의 높이와 너비

문제번호: 2250

정답비율: 26.759%

분류: DFS

비고: 이진트리

풀이 코드

#include <stdio.h>

#include <cstring>

#include <climits>

#include <vector>

using namespace std;

struct NODE {

int left;

int right;

int level = 1;

int label;

} Node[10001];

struct LEVEL {

int min = INT_MAX;

int max = 0;

LEVEL() {}

};

LEVEL Level[10001];

static int levelNum = 0;

void levelUpdate(int nodeNum) {

int l = Node[nodeNum].level;

if (levelNum < l) {

levelNum = l;

}

Level[l].min = (Level[l].min > Node[nodeNum].label) ? Node[nodeNum].label  : Level[l].min;

Level[l].max = (Level[l].max < Node[nodeNum].label) ? Node[nodeNum].label : Level[l].max;

return;

}

void traverseSlave(int curr) {

static int level = 0;

static int cnt = 0;

Node[curr].level = ++level;

if (Node[curr].left != -1) {

traverseSlave(Node[curr].left);

}

Node[curr].label = ++cnt;

if (Node[curr].right != -1) {

traverseSlave(Node[curr].right);

}

level--;

return;

}

int main(void){

freopen("Text.txt", "r", stdin);

int N;

scanf("%d", &N);

int root = 1;

for (int i = 1; i <= N; i++) {

int n, l, r;

scanf("%d %d %d", &n, &l, &r);

if (i == 1) root = n;

Node[n].left = l;

Node[n].right = r;

if ((root == l) || (root == r)) root = n;

}

traverseSlave(root);

for (int i = 1; i <= N; i++) {

levelUpdate(i);

}

int max = 0;

int maxLevel = 0;

for (int i = 1; i <= levelNum; i++) {

int width = Level[i].max - Level[i].min + 1;

if (max < width) {

maxLevel = i;

max = width;

}

}

printf("%d %d", maxLevel, max);

return 0;

}