drop-of-water

문제 링크

조건

  • The number of nodes in the tree is in the range [1, 10^4].
  • -100 <= Node.val <= 100

입력값

  • root = binary tree의 루트 노드
트리 노드는 아래와 같은 형태임
function TreeNode(val, left, right) {
      this.val = (val===undefined ? 0 : val)
      this.left = (left===undefined ? null : left)
      this.right = (right===undefined ? null : right)
 }

출력값

  • 트리의 diameter = 두 node 사이의 가장 긴 거리

풀이과정

  • depth 값이 가장 큰 왼쪽, 오른쪽 child의 거리가 가장 큰 것이 diameter이다
  • dfs 방식으로 왼쪽, 오른쪽 child를 traverse 하면서 가장 큰 depth 값을 가진 왼쪽, 오른쪽 child를 찾는다
  • 가장 큰 depth 값을 가진 왼쪽, 오른쪽 child의 depth를 합한 값이 현재 계산한 diameter 값보다 크다면 diameter 값을 업데이트 한다

코드

var diameterOfBinaryTree = function (root) {
  let diameter = 0;

  // dfs 방식으로 왼쪽, 오른쪽 child를 traverse 하면서
  // 가장 큰 depth 값을 가진 왼쪽, 오른쪽 child를 찾는다
  function maxDepth(root) {
    if (root === null) return 0;
    let left = maxDepth(root.left);
    let right = maxDepth(root.right);

    // 가장 큰 depth 값을 가진 왼쪽, 오른쪽 child의
    // depth를 합한 값이 현재 계산한 diameter 값보다
    // 크다면 diameter 값을 업데이트 한다
    diameter = Math.max(diameter, left + right);

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

  maxDepth(root);

  return diameter;
};

😊