[c++] 이진 트리의 직경(Diameter of Binary Tree)

12 Dec 2023

이진 트리의 직경(Diameter)은 트리의 두 노드 간 가장 긴 경로의 길이를 나타냅니다.

우선, 이진 트리의 직경을 구하는 문제는 다음과 같은 트리 구조의 클래스가 주어졌을 때, C++로 구현할 수 있습니다.

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

그 다음으로, 직경을 계산하는 함수는 다음과 같이 구현할 수 있습니다.

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int result = 0;
        depth(root, result);
        return result;
    }
    
    int depth(TreeNode* node, int& result) {
        if (node == NULL) return 0;
        
        int left = depth(node->left, result);
        int right = depth(node->right, result);
        
        result = max(result, left+right);
        
        return 1 + max(left, right);
    }
};

위의 코드에서는 depth 함수를 활용하여 각 노드의 서브 트리의 깊이를 계산하고, 이를 통해 두 노드 간의 거리를 구하게 됩니다.

결론

이진 트리의 직경을 구하는 문제는 각 노드의 서브 트리의 깊이를 고려하여 효율적으로 해결할 수 있습니다.

또한, 해당 문제에 대한 자세한 내용은 LeetCode에서 확인할 수 있습니다.