Leetcode- Diameter of Binary Tree, CPP

흑빡·2026년 5월 11일

cpp leetcode 알고리즘

알고리즘

목록 보기

9/12

Diameter of Binary Tree

풀이

가장 큰 둘레를 가지는 이진트리의 길이를 반환하면 된다

bfs로 하려고 햇으나 코드가 너무 복잡해져서 dfs로 해결하기로 함

재귀

재귀의 핵심은 DP와 같음

각 재귀의 반환값은 이미 정답임
그럼 어떤 값을 반환해야 원하는 값으로 이용할 수 있을지를 생각

먼저 코드를 보자

class Solution {
public:

    int dfs(int &ans, TreeNode* root) {
        if (!root) return 0;

        int l = dfs(ans, root->left);
        int r = dfs(ans, root->right);

        ans = max(ans, l + r);

        return max(l, r) + 1;
    }

    int diameterOfBinaryTree(TreeNode* root) {
        int ans = 0;
        dfs(ans, root);
        return ans;
    }
};

1. 각 재귀의 반환값은 이미 정답임

int l = dfs(ans, root->left);
int r = dfs(ans, root->right);

이 부분을 생각하기전에, 먼저 이진트리고, left, right가 있음

그러니까, left를 계속 타고가면 어떠한 트리이든,
해당 노드를 루트로 가지는 이진트리의 가장 깊은 왼쪽 노드가 반환되는거임

반대는 오른쪽이고 ㅇㅇ

dfs(root->left);
dfs(root->right);

를 하면 그냥 최고 깊이의 노드가 나타나는거 ㅇㅇ

2. 어떤 값을 반환해야 원하는 값으로 이용할 수 있을지를 생각

지금 원하는 값은 최고 길이가 되는 이진트리의 길이를 구하는거임

즉, 특정노드 n을 기준으로 최고길이가 되는 경우를 따지면 되는데,
이말은 루트노드를 거쳐가며 만들 수 있는 이진트리중 길이가 가장 길이가 긴 이진트리가 정답인 이진트리라는거임

즉, 루트노드에서부터 가장 깊은 left, right노드의 깊이를 합하면 최고 길이를 가지는 이진트리의 길이가 됨

그럼 반환값으로 무엇을 반환해야할까?

현재 노드의 깊이를 반환하면 됨

dfs(root->left);
dfs(root->right);

여기서 dfs메서드의 반환 타입은 노드의 깊이니까 int타입이 되어야함

int l = dfs(root->left);
int r = dfs(root->right);

그리고 dfs에서 반환을 해줘야하니,

int l = dfs(root->left);
int r = dfs(root->right);

return std::max(l,r) + 1;

자신 노드의 자식 노드 중 더 깊은 위치에 있는 노드의 깊이를 반환하면 됨

하지만 이걸론 안됨

3. 정답

가장 깊이가 깊은 노드의 깊이를 구하는 문제가 아님

가장 긴 길이를 가지는 이진트리의 길이를 구하는 문제임

즉, 현재 l과 r의 합이 자신 노드에서 가장 길이가 긴 노드가 됨

따라서

int dfs(int &ans, TreeNode* root) 
{
    if (!root) return 0;

    int l = dfs(ans, root->left);
    int r = dfs(ans, root->right);

    ans = max(ans, l + r);

    return max(l, r) + 1;
}

이런 코드가 완성됨

ans는 변수로 빼도 상관없음

class Solution {
public:
	int ans = 0;
    
    int dfs(TreeNode* root) {
        if (!root) return 0;

        int l = dfs(root->left);
        int r = dfs(root->right);

        ans = max(ans, l + r);

        return max(l, r) + 1;
    }

    int diameterOfBinaryTree(TreeNode* root) 
    {
        dfs(root);
        return ans;
    }
};