내용 |
import java.util.ArrayList;
public class Task1 {
public static void main(String[] args) {
//트리객체 생성
Tree t5 = new Tree(5);
Tree t8 = new Tree(8);
Tree t9 = new Tree(9);
Tree t12 = new Tree(12);
Tree t2 = new Tree(2);
Tree t7 = new Tree(7);
Tree t4 = new Tree(4);
Tree t1 = new Tree(1);
Tree t3 = new Tree(3);
//트리 초기화
t5.l = t8; t5.r = t9;
t8.l = t12; t8.r = t2;
t9.l = t7; t9.r = t4;
t7.l = t1;
t4.l = t3;
preorder(t5);
System.out.println();
int result = solution(t5);
System.out.println("\n" + result);
}
public static int solution(Tree t) {
if(t==null) return 0;
int max = 0;
ArrayList<Integer> amps = new ArrayList<>();
ArrayList<Integer> list = new ArrayList<>();
list.add(t.x); list.add(t.x);
dfs(t, list, amps);
for(Integer amp : amps) {
max = Math.max(amp, max);
}
return max;
}
//재귀 호출을 이용한 깊이우선탐색
public static void dfs(Tree t, ArrayList<Integer> cur, ArrayList<Integer> amps) {
if(t.l==null && t.r==null) amps.add(cur.get(1) - cur.get(0));
System.out.print("(");
System.out.print(t.x);
System.out.print(", ");
if(t.l != null){
ArrayList<Integer> list = new ArrayList<Integer>(cur);
if(t.l.x < list.get(0)) list.set(0,t.l.x);
if(t.l.x > list.get(1)) list.set(1,t.l.x);
dfs(t.l, list, amps);
} else {
System.out.print("None");
}
System.out.print(", ");
if(t.r != null){
ArrayList<Integer> list = new ArrayList<Integer>(cur);
if(t.r.x < list.get(0)) list.set(0,t.r.x);
if(t.r.x > list.get(1)) list.set(1,t.r.x);
dfs(t.r, list, amps);
} else {
System.out.print("None");
}
System.out.print(")");
return;
}
//재귀 호출을 이용한 전위 순회
public static void preorder(Tree t) {
if(t!=null) {
System.out.print("(");
System.out.print(t.x);
System.out.print(", ");
preorder(t.l);
System.out.print(", ");
preorder(t.r);
System.out.print(")");
} else {
System.out.print("None");
}
}
}
class Tree {
public int x;
public Tree l;
public Tree r;
Tree(int x) {
this.x = x;
}
} |