Diameter of Binary Tree - LeetCode

문제 접근 🤔

• 이진 트리의 지름을 구하는 문제
• 이진 트리 혹은 일반적인 트리의 지름을 찾기 위해서는 임의의 두 정점 사이의 간선의 개수가 가장 많을때의 경로를 알아내야 한다.
• 하나의 서브트리에서 가장 긴 경로(지름)는 리프노드 - 리프노드 혹은 루트노드 - 리프노드 의 형태를 가지게 된다.
• 루트노드 - 리프노드 의 경우엔 트리의 높이를 구하면 되지만, 리프노드 - 리프노드 의 경우엔 내부 노드 사이에서 가장 긴 경로가 형성될 수 있기 때문에 다른 아이디어로 접근해야 한다.
• 이를 쉽게 구하기 위해서는 루트노드 - 리프노드 를 구하기 위해 트리의 높이를 구하는 재귀함수 내에서 각각의 서브트리의 루트노드를 기준으로 왼쪽 서브트리 높이 + 오른쪽 서브트리 높이 의 값을 전역변수에 갱신시켜주면 된다.
• 최종적으로는 재귀적인 호출 덕분에 가장 긴 리프노드 - 리프노드 길이를 구할 수 있다.
  
  
  

놓쳤던 부분 😅

• 처음에 문제를 제대로 안 읽고 풀어서 입력 값이 연결 리스트가 아닌 완전 이진 트리를 배열로 나타낸 경우로 문제를 풀이했다 ㅋㅋ 😮‍💨
  
  
  

코드 😁

파이썬 코드(44 ms)

class Solution(object):
    def diameterOfBinaryTree(self, root):
        self.edgeCnt = 0 # 가장 긴 리프 - 리프 경로 길이
        
        def dfs(node):
            if not node: return 0
            left, right = dfs(node.left), dfs(node.right)
            self.edgeCnt = max(self.edgeCnt, left + right)
            return max(left, right) + 1

        dfs(root)
        return self.edgeCnt

# 입력값이 배열의 형태로 주어진다고 생각한 풀이
from math import floor

class Solution:
    def diameterOfBinaryTree(self, root):
        visited = [False for _ in range(len(root))] # 방문 여부 확인
        self.edgeCnt = 0 # 간선의 개수

        def dfs(node, bottomUpMode = True):
            if node == 1:
                bottomUpMode = False # 정점이 1이면 top down 방식으로 변경
                node = 3 if visited[1] else 2 # 아직 방문하지 않은 자식 노드로 내려가자.
						# 노드가 root의 길이보다 길어질 수 없음
            if node > len(root):
                return
            visited[node - 1] = True # 현재 노드 방문 처리
						# bottom up이면 다음 노드는 2로 나눈 몫이고, top down이면 현재 노드에 2를 곱한다.
            nextNode = floor(node / 2) if bottomUpMode else node * 2
            self.edgeCnt += 1
            dfs(nextNode, bottomUpMode)
            return
        
        dfs(root[len(root) - 1]) # 마지막으로 주어진 정점부터 탐색
        return self.edgeCnt

자바스크립트 코드(58 ms)

const diameterOfBinaryTree = (root) => {
  let edgeCnt = 0; // 가장 긴 리프 - 리프 경로 길이

  const dfs = (node) => {
    if (!node) {
      return 0;
    }

    let [leftHeight, rightHeight] = [dfs(node.left), dfs(node.right)];
    edgeCnt = Math.max(edgeCnt, leftHeight + rightHeight);
    return Math.max(leftHeight, rightHeight) + 1;
  };
  dfs(root);
  return edgeCnt;
};