이진트리의 직경을 구해보자! [Java / LeetCode 543]

URL : https://leetcode.com/problems/diameter-of-binary-tree/description/

LeetCode - The World's Leading Online Programming Learning Platform

 오늘은, 이진트리의 직경을 구하는 방법을 공부해 보도록 하겠습니다.

 이진트리의 직경을 구하는 알고리즘을 공부하기에 앞서서, 이진트리의 직경이라는 것이 과연 무엇인지 알아볼까요?

 

이진 트리(Binary Tree)의 직경(Diameter)

 이진트리 내에 포함된 여러 노드들이 있겠죠? 이 노드들 중에서 임의의 노드 2개를 골라서 거리를 구했을 때, 그 거리가 최대가 되는 경우에 그 거리를 이진트리의 직경이라고 합니다. 그림으로 알아보겠습니다.

 

 

 위와 같은 이진트리가 주어져 있다고 가정해 볼까요? 이 경우에서, 이진트리의 직경은 5가 됩니다. 왜냐하면, 이진트리에서 노드와 노드간 거리가 최대가 되는 경우는 A노드와 B노드 사이가 되고, 이 두 노드 사이간의 거리, 즉 A노드를 출발하여 B노드로 가기 위해 경유해야 하는 Edge의 수는 5가 되기 때문입니다.

 

 이상으로 이진트리의 직경이 무엇인지 알아보았습니다!

 

이진 트리(Binary Tree)의 직경(Diameter)을 구하는 방법

 그러면 도대체 이진트리의 직경을 어떻게 구할 수 있을까요?

 트리가 주어져 있을 때에 가장 먼 두 노드간의 거리를 구해야 되는데, 이 가장 먼 두 노드를 각각 어떻게 찾을지도 막막합니다. 하지만! 사실 이 두 노드를 직접 찾을 필요 없이, 간단하게 이진트리의 직경을 구할 수가 있습니다. 

 

"이진트리의 직경 = 이진트리 루트노드의 좌측 자식트리의 깊이 + 우측 자식트리의 깊이"

 

 생각보다 너무 간단해서 어이가 없을 정도인데, 진짜로 그런지 그림으로 알아보겠습니다.

 

 위 그림에서 노란색 부분을 한번 보겠습니다. 노란색 부분을 하나의 트리라고 하였을 때, 이 트리의 직경은 얼마가 될까요? 바로, 좌측 자식노드의 깊이인 1에 우측 자식노드의 깊이인 0에 2를 더한 3으로 계산됩니다.

 

그러면, 이를 자바(Java)를 이용해 구현해 보도록 하겠습니다.

소스 코드

class Solution {
    int diameter = 0;

	// 인자로 전달된 node의 높이를 계산해 리턴하는 함수
    public int dfs(TreeNode node) {
        if(node == null)
            return 0;

        int left = dfs(node.left); // 왼쪽 자식노드의 깊이
        int right = dfs(node.right); // 오른쪽 자식노드의 깊이
        diameter = Math.max(diameter, left + right); // 트리의 직경을 계산해 갱신

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

    public int diameterOfBinaryTree(TreeNode root) {
    	// null인 노드가 전달된다면 깊이가 0 이므로
        if(root == null)
            return 0;

        int depth = dfs(root);
        
        // 노드들을 DFS로 탐색하며 갱신된 최대 직경을 반환
        return diameter;
    }
}

 

 하나하나 살펴봅시다.

 사실 이진트리의 직경을 구하는 문제라고는 하지만, 이 문제의 핵심은 "노드의 깊이를 구하는 함수"입니다.(위에서 dfs라는 이름으로 정의된 함수)

 

트리를 재귀적으로 순회하면서 해당 노드의 깊이를 다음과 같이 계산합니다.

        int left = dfs(node.left); // 왼쪽 자식노드의 깊이
        int right = dfs(node.right); // 오른쪽 자식노드의 깊이
        
        ...
        return Math.max(left, right) + 1; // 해당 노드의 깊이

 

 해당 노드의 높이 = (좌측 자식노드의 높이와 우측 자식노드의 높이중 더 큰 것) + 1

 

dfs라는 함수는 이렇게 현재 노드의 높이가 얼마인지를 계산합니다.

그런데! dfs라는 함수 내에서 현재 노드의 높이가 얼마인지만 계산하는 것은 아닙니다.

다음과 같은 코드가 눈에 띕니다.

	diameter = Math.max(diameter, left + right); // 트리의 직경을 계산해 갱신

아까 해당 트리의 직경은 좌측 자식노드의 높이 + 우측 자식노드의 높이 라고 하였죠?

이렇게 모든 노드를 순회하면서 직경을 업데이트해 나갑니다.

 

즉 이번 문제풀이의 핵심은 다음과 같습니다.

 

"트리의 직경은 좌측 자식노드의 높이 + 우측 자식노드의 높이이다."

"노드의 높이를 구하려면 재귀적 함수 호출의 구조를 띄는 방식으로 설계해야 한다."

"재귀 함수는 노드의 높이를 계산하도록 구현하지만, 그 과정에서 지속적으로 트리의 diameter를 업데이트 해 나간다"

 

이상으로, 이진트리의 직경을 구하는 방법을 알아보았습니다. 감사합니다.