|
leaf node가 n개인 이진 트리를 구하는 것이다.
예를 들어보자
leaf node가 하나인또는 둘인 이진 트리는 한가지 밖에 없다.
아래는 둘인 경우
트리번호
|
노드번호
|
부모노드
|
순서
|
노드값
|
1
|
1
|
|
1
|
|
1
|
2
|
1
|
1
|
1
|
1
|
3
|
1
|
2
|
2
|
이런 형태가 되고
수식 형태로 표현하면 (1+2) 라고 볼 수 있다.
leaf node가 세개 인 경우는 두가지가 있는데
트리번호
|
노드번호
|
부모노드
|
순서
|
노드값
|
1
|
1
|
|
1
|
|
1
|
2
|
1
|
1
|
1
|
1
|
3
|
1
|
2
|
|
1
|
4
|
3
|
1
|
2
|
1
|
5
|
3
|
2
|
3
|
2
|
1
|
|
1
|
|
2
|
2
|
1
|
1
|
|
2
|
3
|
2
|
1
|
1
|
2
|
4
|
2
|
2
|
2
|
2
|
5
|
1
|
2
|
3
|
이런 형태가 된다.
수식형태로 표현하면 (1+(2+3)) 과 ((1+2)+3) 이라고 볼 수 있다.
임의의 숫자를 받아서 leaf-node가 해당 숫자만큼이 되는 모든 이진 트리의 구조를 구하는 것이 문제이다.
답은 두가지 형태로 출력하여도 되는데
한가지는 트리번호,노드번호,부모노드,순서,노드값을 컬럼으로 갖는 위와 같은 형태로 출력하되 노드번호와 부모노드는 위와같이 숫자가 아니어도 상관없다.
두번째 방식은 수식형태로 출력하는 것이다.
즉 숫자가 5라면 다음과 같이 출력하면 된다.
1 + ( 2 + ( 3 + ( 4 + 5 ) ) )
1 + ( 2 + ( ( 3 + 4 ) + 5 ) )
1 + ( ( 2 + 3 ) + ( 4 + 5 ) )
1 + ( ( 2 + ( 3 + 4 ) ) + 5 )
1 + ( ( ( 2 + 3 ) + 4 ) + 5 )
( 1 + 2 ) + ( 3 + ( 4 + 5 ) )
( 1 + 2 ) + ( ( 3 + 4 ) + 5 )
( 1 + ( 2 + 3 ) ) + ( 4 + 5 )
( ( 1 + 2 ) + 3 ) + ( 4 + 5 )
( 1 + ( 2 + ( 3 + 4 ) ) ) + 5
( 1 + ( ( 2 + 3 ) + 4 ) ) + 5
( ( 1 + 2 ) + ( 3 + 4 ) ) + 5
( ( 1 + ( 2 + 3 ) ) + 4 ) + 5
( ( ( 1 + 2 ) + 3 ) + 4 ) + 5
|
