백준 13325: 이진트리 - javascript(트리)

문제 출처 

https://www.acmicpc.net/problem/13325

 

정답 코드 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

let k = Number(input[0]);  // 트리의 높이
let size = Math.pow(2, k + 1) - 1;  // 트리의 전체 노드 수
let arr = new Array(size + 1).fill(0);  // 노드의 가중치를 저장하는 배열

// 트리의 가중치 입력
let weights = input[1].split(' ').map(Number);
for (let i = 2; i <= size; i++) {
    arr[i] = weights[i - 2];  // arr[2]부터 채워넣음
}

let ans = 0;  // 답을 저장할 변수

// DFS 탐색 함수
function dfs(node) {
    // 리프 노드인 경우, 해당 노드의 가중치를 답에 더하고 반환
    if (node * 2 >= size) {
        ans += arr[node];
        return arr[node];
    }

    // 왼쪽 자식과 오른쪽 자식의 값 구하기
    let left = dfs(node * 2);
    let right = dfs(node * 2 + 1);

    // 현재 노드의 값과 자식 노드들의 차이를 더함
    ans += arr[node] + Math.abs(left - right);

    // 부모 노드에게 큰 값을 반환
    return arr[node] + Math.max(left, right);
}

// 루트 노드부터 DFS 시작
dfs(1);

// 결과 출력
console.log(ans);