[BinaryTree][Easy] 543. Diameter of Binary Tree

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

 

주어진 tree의 최대 diameter 길이를 구하라.

diameter란 두 leaf 노드 간 최대 거리를 말하며, 이는 root를 거치지 않을 수 있다.

 

특정 노드를 기준으로 left child와 right child의 max count가 diameter가 된다. 

이 diameter를 모든 노드 기준으로 구하고, 그 중 max 값을 반환한다. 

 

문제는 이 연산을 child count를 구하는 것과 (최적화를 위해) 동시에 처리해야 한다는 것이다.

이것으로 Easy보다는 Medium에 가까운 문제.

 

 

코드 

int diameterOfBinaryTreeDFS(int& maxDiameter, TreeNode* node)
{
    if (node == nullptr)
        return 0;

    int left = node->left!=nullptr ? 1 + diameterOfBinaryTreeDFS(maxDiameter, node->left) : 0;
    int right = node->right!=nullptr ? 1 + diameterOfBinaryTreeDFS(maxDiameter, node->right) : 0;

    // 최대 diameter를 갱신한다.
    maxDiameter = max(left + right, maxDiameter);
    
    // 최대 depth를 반환한다.
    return max(left, right);
}

int diameterOfBinaryTree(TreeNode* root)
{
    int ret = 0;
    diameterOfBinaryTreeDFS(ret, root);
    return ret;
}

 

 

 

결과