543 : Diameter of Binary Tree ( leetcode / java )

 

*해결 과정

 

 리스트에서야 지름 구하는 것을 풀었지 tree에서 지름구하는 문제는 처음입니다. 처음에 root에서 왼쪽 자식의 맨 아래 자손 깊이, 오른쪽 자식의 맨 아래 자손의 깊이를 더해서 출력했는데 틀렸씁니다. 왜냐하면 꼭 루트에서 이어진 길이가 지름이라는 법이 없기 때문입니다. 그래서 각 노드를 모두 root라고 생각하고 순회하면서 비교해야 합니다.

 

리스트, 트리의 지름 = 가장 멀리 떨어져 있는 두 노드의 거리

빨간점을 기준으로 생각해봅시다. 해당 노드에서 지름은 어떻게 구할까요?

다음 2가지를 생각해 보시길 바랍니다.

 

1. 어떻게 해당 노드에서 지름의 길이를 구할 것인가 ( 종료 조건, 재귀로 계산하는 과정, return)

  1-1. 무엇을 return 할 것인가? ( 최대 결과값을 반환 할 것인가, 아니면 다르 값을 반환 할 것인가?)

 

 

 

1. 그림으로 보면 직관적으로 바로 이해할 수 있습니다. 종료 조건은 root가 null일 때입니다. 아무것도 없으니 depth를 0으로 반환하면 됩니다. 재귀로 계산하는 과정은 왼쪽 깊이 + 오른쪽 깊이를 계산하면 됩니다. 

 

  1-1 우리는 재귀로 왼쪽과 오른쪽의 최대 깊이를 구하면서 지름을 구하고 있습니다. 그렇다면 return은 상위 지름의 계산을 위해 "현재 내가 발견한 최대의 깊이 +1"을 하면 됩니다. 높이를 계산하는 것이기 때문에 계속 1만 더해서 반환하되 최대로 긴 길이를 반환하면 됩니다. 그러면서 중간에 answer와 왼쪽깊이 + 오른쪽깊이 와 계속 비교하면서 answer 값을 최신화하면 됩니다.

 

class Solution {
    
    int answer=0;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root==null) return 0;
        DFS(root);
        return answer;
    }
    
    public int DFS(TreeNode root){
        if(root==null) return 0;
        int leftSum = DFS(root.left);
        int rightSum = DFS(root.right);
        answer = Math.max(answer, leftSum+rightSum);
        return Math.max(leftSum,rightSum)+1;
    }
}