ch14-2(leetcode 543). 이진 트리의 직경

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 543번 ( https://leetcode.com/problems/diameter-of-binary-tree/ )

 

 

✅교재를 참고하지 않은 풀이: BFS

 

1차 시도(실패)

 

이진 트리의 직경(diameter)은 가장 거리가 먼 두 노드간의 거리이다. 

그래서 root 노드를 기준으로 왼쪽 subtree에서 가장 root에서 멀리 떨어진 노드와 오른쪽 subtree에서 가장 root와 멀리 떨어진 노드의 거리를 잰 뒤, 둘을 합하면 될 것이라고 생각하고 접근했다. 

 

그러나 예외가 있었다. 

root 노드를 기준으로 불균형이 심한 트리...

 

위의 트리처럼 한쪽 subtree에만 많은 노드가 위치한 경우, root를 기준점으로 나눠서 계산한 직경(=7)보다 하나의 subtree 안의 다른 노드를 기준으로 계산한 직경(=8)이 더 컸다. 

 

class Solution(object):

    def diameterOfBinaryTree(self, root):

        if root is None or (root.left is None and root.right is None):
            return 0

        heightLeft = 0
        heightRight = 0

        queueLeft = collections.deque([root.left])
        queueRight = collections.deque([root.right])

        if root.left is not None:
            while queueLeft:
                heightLeft += 1
                for _ in range(len(queueLeft)):
                    current = queueLeft.popleft()
                    if current.left:
                        queueLeft.append(current.left)
                    if current.right:
                        queueLeft.append(current.right)

        if root.right is not None:
            while queueRight:
                heightRight += 1
                for _ in range(len(queueRight)):
                    current = queueRight.popleft()
                    if current.left:
                        queueRight.append(current.left)
                    if current.right:
                        queueRight.append(current.right)
        
        return heightLeft + heightRight

 

따라서 root 노드만을 기준으로 왼쪽, 오른쪽 subtree의 leaf 노드까지의 거리를 비교하면 안 되고 모든 노드를 기준으로 이 작업을 반복해서 가장 큰 값을 구하면 된다. 

 

✅교재를 참고한 풀이: DFS

 

BFS를 사용하지 않고 DFS를 사용하면 더 간단하게 풀 수 있었다. 

위의 경우 BFS는 맨 위의 root 노드부터 시작했지만 DFS는 leaf 노드에 도달하기 전까지는 탐색을 계속한다. 

 

DFS의 경우 재귀로 구현할 수 있고, 가장 긴 직경 값은 변수를 하나 선언하고 그 값을 업데이트 하면서 진행하면 된다. 그러나 가장 긴 직경 값은 숫자 변수인데, 숫자형은 변할 수 없기 때문에(immutable) 재귀함수 내부에 업데이트 로직을 작성해도 값이 바뀌지 않는다. 

 

그러므로 여기서는 직경 값 변수를 클래스 내부 변수로 선언했다. 이러면 self.longest 으로 해당 클래스 내부 변수에 접근할 수 있으므로 재귀 함수로도 같은 변수에 접근해서 값을 업데이트 할 수 있다. 

class Solution(object):
    longest = 0
    
    def diameterOfBinaryTree(self, root):
        //

 

이제 dfs()를 실행할 재귀함수 내부를 보자. 

재귀함수는 항상 반복적인 코드와 기본 상태(base case)가 필요하다. dfs()는 TreeNode 타입의 노드를 매개변수로 받고 dfs 탐색을 진행한 뒤 해당 노드의 레벨을 숫자로 리턴한다. 이 노드가 null 값일 경우 탐색을 하지 말아야 하므로 이 상태를 base case로 정하자. 

이때, null인 노드는 leaf 노드보다 더 하위 단계에 위치하므로 0이 아니라 -1을 리턴한다. 

if node is None:
    return -1

 

반복 로직의 경우, 한 노드를 기준으로 left subtree, right subtree 각각에 대해 dfs를 실행한다.

left = dfs(node.left)
right = dfs(node.right)

 

반복 로직이 실행되는 경우는 해당 노드가 left, right subtree를 가진 노드라고 볼 수 있다. 

(leaf 노드의 경우, null 값을 갖는 노드를 left, right subtree로 갖고 있다고 볼 수 있다.)

따라서 left, right subtree의 높이를 계산해서 더 큰 것을 선택한 다음에 1을 더해 준다. 해당 노드는 left, right subtree의 부모 노드이기 때문이다. 

return max(left, right) + 1

 

또한 가장 큰 직경 값도 업데이트 해 주어야 한다.

앞서 dfs()에서도 높이를 계산할 때 left, right subtree의 높이에다 1을 더했다.

한 노드를 중심으로 계산한 직경이 가장 크다는 의미는 직경을 계산하는 두 노드가 각각 해당 노드의 left subtree, right subtree에 위치한다는 말이다. 그러므로 두 subtree의 높이를 더한 뒤 1을 두 번 더해야 한다. 

self.longest = max(self.longest, left + right + 2)
return self.longest