[백준 2250] 트리의 높이와 너비(java)- 이진트리,중위순회

문제 보러 가기

2250번: 트리의 높이와 너비

 

이 문제는 이진트리 자료구조를 이용하여 너비를 구하는 응용문제이다. 너비를 구하는 부분에서 좀 다른 점이 있다면, 각 level마다 최대 너비를 구해야 한다는 점. 가장 왼쪽 자식이 1번 , 가장 오른쪽 자식이 n번으로 너비를 구한다는 점이다.

 

아래 트리와 같이 구성된다.

 

 

 

 

 

 

 

문제풀이

- 자신의 번호와(num) 부모 번호(parent) 왼쪽 자식(left) 오른쪽 자식(right)을 갖는 Node 클래스를 만든다.

- Node [] tree 배열에 각 노드의 번호를 담는다.  자식 노드가 존재한다면 자식 노드의 부모 노드를 업데이트.

-> tree 배열에 순서대로 들어가는데 Node마다 자신의 번호를 기록하는 이유 : 루트 노드가 1부터 시작된다는 사항이 없기 때문. 입력은 단순히 노드 번호와 자식 노드의 번호만 주어짐

- parent가 -1일 경우 root노드

 

- 문제에서 각 level마다 너비를 구한 후 최대 너비를 구하기 위해 min [] , max []를 통해 level의 가장 왼쪽 열과 오른쪽 열을 저장한다. -> min [level] = 해당 level에서 가장 왼쪽에 있는 열.

 

ex) 아래 트리에서 min [2] = 3 이 되는 것.

 

 - 트리의 열 번호를 잘 보면 왼쪽부터 -> 부모 -> 오른쪽으로 번호가 매겨지는 것을 알 수 있다.

이 순서대로 탐색하면 번호를 매길 수 있다는 것.  왼쪽 -> 부모 -> 오른쪽 순서는 중위 순회이다.

 

- 중위 순회를 하면서 level마다 가장 왼쪽 열의 번호와 오른쪽 열의 번호를 min [], max []에 업데이트한다.

- max [level]-min [level]로 가장 큰 너비를 구해서 답을 출력한다.

 

 

 

 

 

 

 

public class Ex_2250 {

	static Node[] tree;
	static int[] min,max; // level마다 왼쪽열,오른쪽열 기록
	static int nodeIdx=1; //1번 열부터 순서대로 ++
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		//트리 - 트리의 높이와 너비
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		tree = new Node[n+1];
		int root = 0;
		min = new int[n+1];
		max = new int[n+1];
		
        //트리와 min,max배열 초기화
		for(int i=0;i<=n;i++) {
			tree[i]=new Node(i,-1,-1);
			min[i] = n;
			max[i] = 0;
		}
		
		for(int i=1;i<=n;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int num = Integer.parseInt(st.nextToken());
			int left = Integer.parseInt(st.nextToken());
			int right = Integer.parseInt(st.nextToken());
			
			tree[num].left = left;
			tree[num].right = right;
            
            //자식 노드가 존재한다면 자식노드의 parent에 현재 번호(num)업데이트
			if(left != -1) tree[left].parent = num;
			if(right != -1) tree[right].parent = num;
		}
        
        //부모노드 없을경우 root노드
		for(int i=1;i<=n;i++) {
			if(tree[i].parent==-1) {
				root = i;
				break;
			}
		}
        //루트부터 중위순회
		inorder(root,1);
		int level=1;
		int width=0;
		
        //가장 큰 너비구함
		for(int i=0;i<=n;i++) {
			int tmp = max[i]-min[i];
            //동일 너비가 있을경우 작은 level로 구하기 때문에 <=가 아님
			if(width < tmp) {
				level = i;
				width = tmp;
			}
		}
		System.out.println(level+" "+(width+1));
	}
    //왼쪽자식->root(부모노드)->오른쪽자식
	static void inorder(int root,int level) {
		Node cur = tree[root];
		//왼쪽
		if(cur.left!=-1)
			inorder(cur.left,level+1);
		//root
		min[level] = Math.min(min[level], nodeIdx);
	    max[level] = Math.max(max[level], nodeIdx);
	    nodeIdx++;
	    //오른쪽
	    if(cur.right!=-1)
	    	inorder(cur.right,level+1);
	}
	static class Node{
		int num;
		int parent;
		int left;
		int right;
		
		Node(int num,int left,int right){
			this.num = num;
			this.parent = -1;
			this.left = left;
			this.right = right;
		}
	}

}