[알고리즘] LeetCode diameter of Binary Tree JS

개요

주어진 이진트리에서 지름을 구하는 문제이다. 이때 지름은 정점과 정점 간의 길이 중에서 가장 긴 길이를 지름이라고 한다.

Diameter of Binary Tree - LeetCode

 

풀이

DFS로 풀어야한다는 것은 쉽게 눈치챌 수 있었다.

 

그런데 탐색하면서 계산해야 되는 길이를 어떻게 계산해야하는지 쉽게 떠올리지 못했다. 매번 DFS를 풀때나 BFS 풀때 노드의 레벨로 접근해서만 풀다보니 이번 문제처럼 역순으로 값을 가지고 올라와야할 때 조건을 쉽게 찾지 못했다.

DFS를 피보나치처럼 구현하는 부분일때라고 생각된다.

 

 

하지만 나는 스스로 코드를 작성하면서 DFS 구현과 이해 자체는 문제가 없다고 생각한다. 조건을 더 생각해보고 수학과 구현에 대해 조금 더 이해할 필요가 있다고 생각한다.

 

결국 Discuss를 참고하긴했지만 어느 부분이 문제였는지는 확실히 해야될거같았다.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 *
 * 지름을 구해라
 * 지름은 이진트리 안에서 가장 멀리 떨어진 노드간에 길이이다.
 *
 * 루트를 통과하거나 통과하지않을 수도 있다.
 *
 * 각 루트노드마다 길이를 구해서 최대값으로 활용한다.
 *
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function (root) {
  let answer = 0;

  const DFS = (node) => {
    if (node === null) return 0;

    const left = DFS(node.left);
    const right = DFS(node.right);

    answer = Math.max(answer, left + right);

    return 1 + Math.max(answer, left + right);
  };

  DFS(root);

  return answer;
};