543. Diameter of Binary Tree

문제

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

풀이

class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        DFS(root);
        return max;
    }

    public int DFS(TreeNode node) {
        if(node == null) {
            return 0;
        }

        int left = DFS(node.left);
        int right = DFS(node.right);

        max = Math.max(max, left + right);

        return Math.max(left, right) + 1;

    }
}

• 왼쪽 경로의 깊이 + 오른쪽 경로의 깊이의 최대값이 최대 지름
• DFS는 *현재 노드를 루트로 하는 서브트리의 "최대 깊이"를 반환
• 서브트리마다 지름의 최대값을 구하여, 결과적으로 트리 전체의 지름의 최대값을 구함