내용

글번호 119
작성자 heojk
작성일 2017-01-03 12:27:40
제목 코딩서험 - DFS 알고리즘을 이용한 트리 순회 및 최대 Amplitude값 출력하기
내용 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; } }
첨부파일 Task1.java (2,219byte)