43. Diameter of Binary Tree

🎯 leetcode - 543. Diameter of Binary Tree

---

📌 문제

- 파이썬 알고리즘 인터뷰 43번 문제

📌 날짜

2020.02.15

📌 시도 횟수

4 try / Failed

💡 Code

class Solution:
    longest = 0 # *클래스 변수를 사용한 이유?

    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        def dfs(node):
            if not node: # 존재하지 않는 노드에도 -1 값을 부여함
                return -1

            left = dfs(node.left) # 리프노드까지 재귀 dfs 실행
            right = dfs(node.right) # 리프노드까지 재귀 dfs 실행

            self.longest = max(self.longest, left + right + 2) # 가장 긴 경로 갱신
            return max(left, right) + 1 # 리프노드부터 루트까지 차례대로 리턴

        dfs(root)
        return self.longest

💡 문제 해결 방법

- 리프노드까지 탐색한 다음 다시 루트까지 거슬러 올라가면서 차례대로 현재 노드의 상태값과,
최대 경로 길이 값을 갱신해준다.

- 현재 노드의 상태값은 존재하지 않는 노드를 기준으로, 상위 루트로 이동할수록 1씩 증가한다.
위의 이진 트리 사진에 옅은 색으로 적어둔 값이 바로 해당 노드의 상태값이다.

- 상태값을 구하는 코드는 아래와 같다.
>> max(left, right) + 1

- 리프노드부터 현재 노드까지의 최대 경로 길이는 다음과 같이 구한다. (현재 노드는 node)
>> left(node.left의 상태값) + right(node.right)의 상태값 + 2

- 따라서 최대 경로 길이(longest)를 갱신하는 코드는 아래와 같다.
>> self.longest = max(self.longest, left + right + 2)

💡 새롭게 알게 된 점

😺DFS 탐색 순서는 위의 이진 트리 그림을 기준으로 "1>3>2>5>4" 이다.
따라서 다시 거슬러 올라갈때는 "4>5>2>3>1"의 순서로 상태값이 정해진다.

😺왜 최대 경로 길이(longest)를 클래스변수로 선언하여 사용했을까?
- 위의 코드에서 dfs를 중첩함수로 만들었다.
- 중첩함수는 부모 함수의 변수를 자유롭게 읽을 수 있다.
- 그러나 중첩 함수에서 부모 함수의 변수를 재할당하게 되면 참조 ID가 변경되어 
그냥 별도의 로컬 변수로 선언되어 버린다.
- 따라서 위의 예시처럼 longest의 값을 계속해서 조작하여 사용하려면 
클래스 변수로 빼버려야된다.
- 참고로 list, dict의 경우 append()등의 메소드를 이용해 재할당 없이 조작이 
가능하지만, 문자/숫자의 경우 불변 객체이기 때문에 중첩함수 내에서는 값을 변경할 수 없다.

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 처음에는 루트를 기준으로 왼쪽노드, 오른쪽 노드를 각각 루트로 해서
양쪽의 최대 깊이를 더한 값이 곧 가장 긴 경로의 길이라고 생각했다.
- 그러나 이 생각에는 오류가 있었다!
- 어떤 오류인지 아래 그림을 참고😺

1. 루트를 기준으로 왼쪽, 오른쪽의 최대 깊이를 더한 결과 → 길이= 8
   
2. 실제로 두 노드간 가장 긴 경로 → 길이 = 9
   

이처럼 결과값에 차이가 생간다! 
최대 길이가 무조건 루트를 지날거라는 생각이 틀렸다.
따라서 1번 방법으로 풀면 안된다~👽

---