[Leetcode 543] Diameter of Binary Tree

문제 링크

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

이 문제는 트리의 직경을 구하는 문제로, 트리 안의 두 노드를 잇는 경로 중 최장 경로를 찾는 문제이다.

일단, 트리의 정점들을 모두 찾아봐야하므로, DFS혹은 BFS 풀이가 떠오르는 것이 일반적이다.

이 경우 재귀 DFS로 접근하는 것이 코드가 더 깔끔하므로 DFS로 접근해보자.

일단, 최장 길이 경로에 현재 노드가 포함될 수도 있고, 아닐 수도 있다.

💡 현재 노드가 최장 길이 경로에 포함 되는 경우는, 최장 길이가 왼쪽 서브트리의 깊이(depth(left)) + 오른쪽 서브트리의 깊이depth(right)가 될 것이다.
💡 그렇지 않은 경우에는, 왼쪽 서브트리나 오른쪽 서브트리에 최장 경로가 존재할 것이다.

즉, 최장 경로의 길이(longest)는 Math.max(longest, depth(left) + depth(right))이 된다. 최장 경로에 현재 노드가 포함되지 않는다면 기존 longest를 택하고, 현재 노드가 포함된다면 depth(left) + depth(right)를 택하면 되기 때문이다.

이렇게 DFS로 최장 경로를 구한 뒤, longest를 리턴하면 된다.

⚠️ 재귀로 최대 깊이를 리턴받아야 하므로, 기존 함수로만 깊이를 구하고 longest를 갱신해나간다면, longest는 정상적으로 갱신되나, 결국 root에서의 최대 깊이를 리턴하게 되므로, 헬퍼 함수가 필요하다.

class Solution {
    private int longest = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return longest;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = dfs(root.left);
        int right = dfs(root.right);
        longest = Math.max(longest, left + right);
        return Math.max(left, right) + 1;
    }
}