99클럽(2기) - 코테스터디 8일차 TIL # Binary Tree # DFS # 재귀

LeetCode - 104. Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

---

 

1. 나의 풀이(accepted 되었지만 올바른 풀이 방식이 아님!)

 루트 노드를 기준으로 리프 노드 방향으로 왼쪽 자식 노드들의 간선의 개수, 오른쪽 자식 노드들의 간선의 개수를 각각 세어서 그 둘 중 최대값을 2로 나눈 몫에 1을 더한 값을 반환하면 된다고 생각했다.

 

 간선의 개수를 2로 나눈 몫에 1을 더한 값이 깊이라고 생각한 이유는 하나의 부모 노드와 그에 대한 자식 노드로 이루어진 서브트리는 자식 노드가 하나여서 간선이 1개이든, 자식 노드가 둘이어서 간선이 2개이든, 깊이가 2 // 1 + 1 = 2, 2 // 2 + 1 = 2로 모두 2이기 때문이다. 

 

 더 이상 남은 노드가 없으면 None을 반환하면서 함수를 종료시켰다. 

 

1) 전역변수로 left_edges, right_edges 초기화

left_edges, right_edges를 0으로 초기화한다.

 

2) 왼쪽 노드와 오른쪽 노드에 대해서 각각 재귀로 깊이 증가

max_depth 함수를 재귀적으로 호출할 때마다 전역변수 left_edges, right_edges를 1씩 더한다.

 

3) 최대 간선수 // 2 + 1로 최대 깊이를 계산해서 반환 

모든 왼쪽 노드의 간선들과 모든 오른쪽 노드의 간선들의 개수 중 최대값을 구하고, 해당 값을 2로 나눈 몫에 1 더해 깊이를 계산해서 반환한다. 

 

4) 더 이상 남은 노드가 없으면 None 반환

마지막 노드라면 None을 반환해서 재귀함수를 종료시킨다. 

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
        
class Solution:
    def __init__(self):
        self.left_edges = 0
        self.right_edges = 0

    def max_depth(self, root: Optional[TreeNode]) -> int:
        if root is None: 
            return
        
        self.left_edges += 1
        self.right_edges += 1
        
        self.max_depth(root.left)
        self.max_depth(root.right)

        return max(self.left_edges, self.right_edges) // 2 + 1

 

 

2. 나의 풀이에 대한 Chat GPT의 피드백

 채찍피티에게 나의 풀이에 대해서 피드백해달라고 했는데 아래와 같은 이유로 적절하지 않다고 한다..🥹 퓨 그렇다면 정답처리가 왜 된거지?! 그 이유는 이 문제가 이진 트리 문제였기 때문이다. 만약 이 문제가 균형잡혀 있지 않은 트리에 대한 문제였다면 틀렸을 것이다. 이상적인 풀이는 어떤 트리에도 적용할 수 있도록 각 노드에 대한 독립적인 연산을 재귀적으로 수행해야 하는 것 같다.

 

1) 전역변수로 left_edges, right_edges 초기화

👉🏻 전역변수 left_edges, right_edges 는 트리의 모든 노드에서 공유되기 때문에 특정 노드의 깊이를 독립적으로 계산할 수 없다.

 

2) 왼쪽 노드와 오른쪽 노드에 대해서 각각 재귀로 깊이 증가

👉🏻 left_edges와 right_edges는 모든 재귀 호출에서 공유되고 있다. 왼쪽 서브트리, 오른쪽 서브트리 각각 깊이를 증가시키는 상황을 의도했다고 생각했으나 모든 재귀호출이 끝났을 때 left_edges의 값과 right_edges의 값은 동일했다. 

 

3) 최대 간선수 // 2 + 1로 최대 깊이를 계산해서 반환 

👉🏻 트리가 균형잡혀 있지 않은 경우에는 간선 수 // 2 + 1로 트리의 깊이를 구할 수 없다. 

 

4) 더 이상 남은 노드가 없으면 None 반환 

👉🏻 나는 마지막 노드에 도달했을 때 재귀 함수를 끝내겠다는 의미로 None을 반환했지만 DFS에서 재귀함수를 제대로 사용하려면 rerturn 값을 상위 호출 함수에게 전달해줘야 한다. 

 

---

3. 올바른 풀이

1) 루트 노드에서 시작해 왼쪽 서브트리와 오른쪽 서브트리 각각 리프노드에 닿을 때까지 재귀함수를 통해 자식 노드로 이동

2) 리프 노드에 도달하면 0을 반환해서 부모 노드에 전달

3) 자신의 양쪽 서브트리의 깊이 값을 전달받은 부모 노드는 그 중 최대값에 1을 더해 실제 깊이를 반환

➡️ 각 노드의 왼쪽과 오른쪽 서브트리의 깊이를 독립적으로 계산한 결과가 부모노드에 전달하는 로직이 루트에 도달할 때까지 재귀적으로 반복된다.

 

※ 들여쓰기 수준이 같은 연산은 재귀의 depth가 같습니다. 

 1️⃣ 루트 (노드 3)에서 시작

   - 루트 노드는 None이 아니므로 반환값 없이 pass

   - 루트 노드인 3에서 왼쪽 노드의 깊이를 계산하기 위해 max_depth(root.left)를 호출해서 노드 9로 이동

   - 루트 노드인 3에서 오른쪽 노드의 깊이를 계산하기 위해 max_depth(root.right)를 호출해서 노드 20으로 이동

 

        2️⃣ 루트의 왼쪽 자식 노드 (노드 9)

          - 노드 9는 None이 아니므로 반환값 없이 pass

          - 노드 9에서 왼쪽 노드(root.left = None)의 깊이를 계산하기 위해 max_depth(None)을 호출하면 0을 반환

          - 노드 9에서 오른쪽 노드(root.right = None)의 깊이를 계산하기 위해 max_depth(None)을 호출하면 0을 반환

          - 노드 9의 왼쪽 노드의 깊이 0, 오른쪽 노드의 깊이 0중 큰 값에 1을 더한 값은 1(max(0, 0) + 1 = 1)

          - 따라서 노드 9의 깊이는 1

 

        3️⃣ 루트의 오른쪽 자식 노드 (노드 20 이하) 

          - 노드 20는 None이 아니므로 반환값 없이 pass

          - 노드 20의 왼쪽 노드의 깊이를 계산하기 위해 max_depth(root.left)를 호출해서 노드 15로 이동

          - 노드 20의 오른쪽 노드의 깊이를 계산하기 위해 max_depth(root.right)를 호출해서 노드 7으로 이동

 

                4️⃣ 노드 20의 왼쪽 노드이자 리프노드인 노드 15에서 최초의 깊이 반환

                  - 노드 15는 None이 아니므로 반환값 없이 pass

                  - 노드 15에서 왼쪽 노드(root.left = None)의 깊이를 계산하기 위해 max_depth(None)을 호출하면 0 반환

                  - 노드 15에서 오른쪽 노드(root.right = None)의 깊이를 계산하기 위해 max_depth(None)을 호출하면 0 반환

                  - 노드 15의 왼쪽 노드의 깊이 0, 오른쪽 노드의 깊이 0중 큰 값에 1을 더한 값은 1(max(0, 0) + 1 = 1)

                  - 노드 15의 깊이는 1

 

                5️⃣ 노드 20의 오른쪽 노드이자 리프노드인 노드 7에서 최초의 깊이 반환

                  - 노드 7은 None이 아니므로 반환값 없이 pass

                  - 노드 7에서 왼쪽 노드(root.left = None)의 깊이를 계산하기 위해 max_depth(None)을 호출하면 0 반환

                  - 노드 7에서 오른쪽 노드(root.right = None)의 깊이를 계산하기 위해 max_depth(None)을 호출하면 0 반환

                  - 노드 7의 왼쪽 노드의 깊이 0, 오른쪽 노드의 깊이 0중 큰 값에 1을 더한 값은 1(max(0, 0) + 1 = 1)

                  - 노드 7의 깊이는 1

 

        6️⃣ 노드 20으로 돌아와서 서브트리의 최대 깊이 계산

          - 왼쪽 노드 깊이는 노드 15의 깊이인 1

          - 오른쪽 노드 깊이는 노드 7의 깊이인 1

          - 노드 20의 왼쪽 노드의 깊이 1, 오른쪽 노드의 깊이 1중 큰 값에 1을 더한 값은 2(max(1, 1) + 1 = 2)

 

7️⃣ 루트(노드 3)로 돌아와서 트리의 최대 깊이 계산

  - 왼쪽 노드 깊이는 노드 9의 깊이인 1

  - 오른쪽 노드 깊이는 노드 20의 깊이인 2

  - 노드 3의 왼쪽 노드의 깊이 1, 오른쪽 노드의 깊이 2중 큰 값에 1을 더한 값은 3(max(1, 2) + 1 = 3)

  - 따라서 주어진 트리의 최대 깊이는 3

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        

class Solution:
    def max_depth(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return 0 

        left_depth = self.max_tree(root.left)
        right_depth = self.max_tree(root.right)
        
        return max(left_depth, right_depth) + 1

 

 

4. 다른 사람의 풀이

 뇌용량의 한계를 느끼게 하는 한 줄 풀이다. 리프 노드에 도달해 더 이상 자식 노드가 없을 때는 0을 반환해 상위 호출 함수에 전달하고, 노드가 있을 때는 재귀적으로 왼쪽 서브트리와 오른쪽 서브트리의 깊이를 확인하여 그 중 최대값을 반환한다는 한다는 핵심만 남겼다. 

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        

class Solution:
    def max_depth(self, root: Optional[TreeNode], num=0) -> Optional[TreeNode]:
        return max(self.max_depth(root.left, num+1), self.max_depth(root.right, num+1)) if root else num

 

 

5. 느낀점

 나는 재귀함수를 사용하긴 했지만 각 노드에 대한 독립 연산을 재귀적으로 수행한 것이 아니라, 트리 깊이에 대한 전역변수를 공유하면서 전체 트리를 탐색했다. 하지만 올바른 풀이는 깊이에 대한 전역변수 초기 설정 없이 재귀함수를 통해 자식 노드를 탐색하고 리프노드에 도달하면 최대 깊이를 계산해 부모 노드에 해당 값을 전달하는 과정을 루트 노드까지 반복하는 것이었다. 이번 문제를 통해 DFS에서 재귀를 정확히 사용하는 방법에 대해서 배울 수 있었다. 더 나아가 언젠가는 한 줄 풀이가 머리에 딱! 떠오르는 날이 왔으면 정말 좋겠다..! 

 

 

6. 참고

https://www.youtube.com/watch?v=7C9RgOcvkvo

https://velog.io/@eddy_song/you-can-solve-recursion

야, 너두 재귀할 수 있어: 재귀가 풀리는 4단계 접근법