LeetCode 543 - Diameter of Binary Tree (Easy)

문제

LeetCode - 543번

풀이 과정

이진트리의 지름을 구하는 문제입니다.

이진트리 혹은 일반적인 트리의 지름을 찾기 위해서는 임의의 두 정점 사이의 간선의 개수가 가장 많은 경로를 알아내야합니다.

우선 root 를 루트 노드로 가지는 트리가 다음과 같이 두 가지가 존재할 수 있습니다.

  1
 / \  
 2  3
 /\  
4  5  

    1
   /  
  2  
 / \  
4   5  

위 그림에서는 이진 트리를 가정했지만 일반적인 트리에서도 동일하게 적용됩니다.

따라서 하나의 서브트리에서 가장 긴 경로(지름)는 잎노드 - 잎노드 혹은 루트노드 - 잎노드 의 형태를 가지게 됩니다.

루트노드 - 잎노드 의 경우 트리의 높이를 구하면 되지만 잎노드 - 잎노드 의 경우 내부 노드 사이에서
가장 긴 경로가 형성될 수 있기 때문에 다른 아이디어가 필요합니다.

이를 쉽게 구하기 위해서는 루트노드 - 잎노드 를 구하기 위해 트리의 높이를 구하는 재귀함수 내에서
각각의 서브트리의 루트노드를 기준으로 왼쪽 서브트리 높이 + 오른쪽 서브트리 높이 의 값을 전역변수에 갱신시켜줍니다.

최종적으로는 재귀적인 호출 덕분에 가장 긴 잎노드 - 잎노드 길이를 구할 수 있고 이를 트리의 높이와 비교해주면 됩니다.

코드

/**
 * 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 longest = 0; // 가장 긴 잎-잎 경로 길이

  function dfs(root) {
    if (!root) {
      return 0;
    }

    const leftHeight = dfs(root.left);
    const rightHeight = dfs(root.right);

    longest = Math.max(longest, leftHeight + rightHeight);
    return Math.max(leftHeight, rightHeight) + 1;
  }

  const h = dfs(root) - 1;
  return Math.max(longest, h);
};