Leetcode: Diameter of Binary Tree

Diameter of Binary Tree

Binary Tree 가 주어 졌을때 가장 긴 diameter 구하시오. 예: Binary Tree 가
출처 wikipedia
주어졌다면 [11, 6, 7, 2, 5, 9, 4] 나 [5, 6, 7, 2, 5, 9, 4] 둘다 제일큰 diameter 6 을 가지고 있습니다. 따라서 답은 6입니다.

이 문제는 depth 를 구하는 식으로 구할 수 있습니다. 7 을 보죠 7의 왼쪽 depth은 1 오른쪽 depth은 2임을 알 수 있습니다. 그럼 7의 최대 diameter 는 1 + 2 = 3 이 될것입니다.

private int maxDia;
public int diameterOfBinaryTree(TreeNode root) {
    depth(root);
    return maxDia;
}
private int depth(TreeNode node) {
    if (node == null) return 0;
    int leftDepth = depth(node.left);
    int rightDepth = diameter(node.right);
    maxDia = Math.max(depth+ rightDepth, maxDia);
    return Math.max(leftDepth, rightDepth) + 1;
}