포화이진트리 - 각 가중치 총합을 최소로 만들기

// 각각의 엣지에 가중치가 있는 포화 이진 트리가 있다.
// 루트에서 각 리프까지의 경로 상 가중치 합을 각각 같게 하고,
// 모든 가중치들의 총합이 최소가 되도록 하는 프로그램을 작성하세요.

 

- 포인트 1. 엣지를 트리로 보기

- 포인트 2. 후위 순회하기..

- 포인트 3. 차이를 더해주기 ==> += Math.abs(x - y);

- 포인트 4. 높이로 포화이진트리 담을 배열의 길이 구하기 --> 정답 풀이 케이스에서 활용 ==> Math.pow(2, h + 1);

public class MyCode { // 후위 순회 --> 트리 문제 풀때 무슨 순회인지 먼저 파악하기 !

    public static void solution(int h, int[] w) { // 후위 순회..  // 엣지를 노드처럼 활용.
        // 블로그 하기..
        Tree tree = new Tree(w, h);
        tree.postOrder(0, 0); 
        // 전체 가중치 + 새로 더해진 값...
        System.out.println(Arrays.stream(w).sum() + tree.res);
    }
    
    static class Tree {
        int res = 0;
        int[] edges;
        int height;

        Tree(int[] arr, int height) {
            edges = new int[arr.length + 1];
            for (int i = 1; i < edges.length; i++) { // 루트 노드 0으로 비우기
                edges[i] = arr[i - 1];
            }
            this.height = height;
        }

        //     0                   0
        //  2     2      ->     3     2
        // 2 1   1 3           2 2   3 3
        int postOrder(int h, int idx) {
            if (h == this.height) {
                return edges[idx]; //
            }

            int left = postOrder(h + 1, idx * 2 + 1);
            int right = postOrder(h + 1, idx * 2 + 2);

            // 후위 순위 -> 좌우 순회 후 로직 처리...!
            res += Math.abs(left - right); //차이 더해주기 (같게 만들기) 
            return edges[idx] + Math.max(left, right);
        }
    }
    
    public static void main(String[] args) {
        // Test code
        int h = 2; //트리의 높이
        int[] w = {2, 2, 2, 1, 1, 3}; // 트리에서 각각 에지의 가중치
        solution(h, w);
        System.out.println();

        h = 3;
        w = new int[]{1, 2, 1, 3, 2, 4, 1, 1, 1, 1, 1, 1, 1, 1};
        solution(h, w);
    }
}