Tree

종이 접기
종이를 반으로 접었을때 안으로 파인 부분은 0, 튀어나온 부분이 1
종이를 접을 때는 오른쪽에서 왼쪽으로
종이를 N번접을때 접힌 상태를 출력
in out
1 0
2 0, 0, 1
3 0, 0, 1, 0, 0, 1, 1

public class test {

  public static void solution(int n) {
    int[] tree = new int[(int) Math.pow(2, n)];

    tree[0] = 0; // 처음무조건 0
    for (int i = 0; i < (int) Math.pow(2, n - 1) - 1; i++) {
      tree[i * 2 + 1] = 0; // left
      tree[i * 2 + 2] = 1; // right
    }

    inOrder(tree, 0);
    System.out.println();
  }

  public static void inOrder(int[] arr, int idx) {
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    if (left < arr.length - 1) {
      inOrder(arr, left);
    }

    System.out.print(arr[idx] + " ");

    if (right < arr.length - 1) {
      inOrder(arr, right);
    }
  }

  public static void main(String[] args) throws Exception {
 
    solution(1);
    solution(2);
    solution(3);
  }

}

각각의 엣지에 가중치가 있는 포화이진트리
루트에서 각 리프까지의 결로 길이를 모두 같게 해야함
모든 가중치들의 총합이 최소가 되도록

class Tree {
  int h;
  int[] arr;
  int res;

  public Tree(int h, int[] w) {
    this.h = h;
    arr = new int[(int) Math.pow(2, h + 1)];
    res = 0;

    for (int i = 2; i < (int) Math.pow(2, h + 1); i++) {
      arr[i] = w[i - 2];
    }
  }

  public int dfs(int idx, int h) {
    if (this.h == h) {
      res += arr[idx];
      return arr[idx];
    }

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

    res += arr[idx] + Math.abs(left - right);
    return arr[idx] + Math.max(left, right);
  }
}

public class test {

  public static void solution(int h, int[] w) {
    Tree tree = new Tree(h, w);
    tree.dfs(1, 0);
    System.out.println(tree.res);

  }

  public static void main(String[] args) throws Exception {
    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);
    System.out.println();

  }

}