리트코드) 543. 이진 트리의 직경(자바)

이진 트리의 직경

문제 : 이진트리에서 두 노드가 가장 긴 경로의 길이를 출력하라.

• 이진 트리의 루트가 주어지면 트리 지름의 길이를 반환합니다.
• 이진 트리의 직경은 트리의 두 노드 사이에서 가장 긴 경로의 길이입니다.
• 이 경로는 루트를 통과할 수도 있고 통과하지 않을 수도 있습니다.
• 두 노드 사이의 경로 길이는 두 노드 사이의 간선 수로 표시됩니다.

예시 1

입력: root = [1,2,3,4,5]
출력: 3
설명: 3은 경로 [4,2,1,3] 또는 [5,2,1,3]의 길이입니다.

예시 2

입력: 루트 = [1,2] 출력: 1

풀이

이 문제는 이해하는 것이 절반이다.
루트기준 좌에서 가장 긴 + 우에서 가장 긴 으로 생각할 수 있는데 아니다.
“이 경로는 루트를 통과할 수도 있고 통과하지 않을 수도 있습니다.”라는 조건은 루트 상관 없이 두 노드간 가장 긴 길이를 구하는 문제였다.

그래서 (노드에서 왼쪽 가장 깊은 깊이 + 오른쪽 가장 깊은 깊이) vs (가장 깊은 깊이)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int longest = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) {
            return -1;
        }
        calc(root, 0); // depth는 0부터 시작
        return longest;
    }

    // 길이 구하기
    public int calc (TreeNode root, int depth) {
        if(root == null) {
            return 0;
        }
        int left = calc(root.left, depth);
        int right = calc(root.right, depth);
        longest = Math.max(longest, left + right); // 왼+오 중 더 깊은 깊이는?
        return Math.max(left, right) + 1;  // depth +=1
    }
}