[Binary Tree][Easy] Diameter of Binary Tree

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

 

Q. 주어진 Binary Tree의 최대 경로의 길이를 찾아라. 

 이 최대 경로는 root를 지나지 않을 수 있다.

 

Solution. 

 우선 Binary Tree에서 최대 경로에 대한 정의를 찾아 본다. 

 특정 노드를 기준으로 left와 right를 연결한 길이가 최대가되면 그 경로를 최대 경로라 정의한다. 

4 - 2 - 1 - 3    혹은  5 - 2 - 1- 3 이 최대 경로가 된다. 

 

위 트리의 최대 경로는 보는 바와 같이 root를 지나지 않는다. 

 

-1 0 6 9 -9 -7 -6 9 -2 혹은

-4 6 6 9 -9 -7 -6 9 -2이 최대 경로가 된다. 

 

그럼 이 경로를 어떻게 구할까. 

 

특정 노드에서 왼쪽 node depth의 최대값, 

오른쪽 node depth의 최대값을 더하면 될 것이다. 

 

즉, 특정 노드 안에서 

노드 왼쪽 최대값을 구하고, 

오른쪽 최대값을 구하고 

이 두 값을 사용해 트리의 최장 경로를 갱신한다. 

그리고 이 노드에서는 왼쪽, 오른쪽 중 더 큰 depth를 반환한다.

 

이를 코드로 적는다. 

 

    int maxDOBT_BFS(TreeNode* node, int& ret, int len)
    {
        if (node == NULL)	return len;

        int left = maxDOBT_BFS(node->left, ret, len+1);
        int right = maxDOBT_BFS(node->right, ret, len+1);

        // 현시점에서의 depth제거, 또한 경로의 두 edge제거.
        ret = max(ret, left + right - 2*len - 2);
        
        return max(left, right);
    }
public:
    int diameterOfBinaryTree(TreeNode* root)
    {
        int ret = 0;
        maxDOBT_BFS(root, ret, 0);
        return ret;
    }

 

적절한 결과를 얻었다.