흥미로운 IT

트리 이론을 공부한 후 가장 처음으로 건드려보려고 한 문제가 바로 이 문제다.

preorder (root --> left --> right) traversal의 순서는 알았지만, 

정확히 이것을 리스트로 받고 처리를 하는 것인지에 대해서 고민이 많았다.

그리고 현재 계속 "재귀"에 대한 이해를 제대로 잡고 가기 위해서 이번에는 재귀를 제대로 잡자는 생각으로 재귀로 코드를 짜 보고자 하였다.

우선 과거에 자료구조를 공부할 때, C언어로 잠깐했었는데, 언뜻 기억났던 코드가 바로 다음과 같은 코드였다.

void traversal(node){
    if ( node){
        visit(node); preorder
        traversal(node -> left);
        #visit(node); inorder
        traversal(node -> right);   
        #visit(node); postorder
    }  
}

그럼 위의 코드를 이제 리트코드에 준 문제에 맞게 만들어야 했는데,

정말로 고민을 많이 했다.

어디서 어떻게 코드가 들어가야 하고,

재귀는 정확히 어떻게 이루어지는지가 고민이었다.

# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        visited = []
        if root is not None:
            visited.append(root.val)
            # print(root.val, "afterAppend", visited)
            visited.extend(self.preorderTraversal(root.left))
            # print(root.val, "afterLeft", visited)
            visited.extend(self.preorderTraversal(root.right))
            # print(root.val, "afterRight", visited)
        return visited

여기서 visited.extend도 핵심이다.

처음에 나는 그냥 self.preorderTraversal(root.left)라고 했었다.

그런데 이렇게 하다보니, visited를 return 했을 때, 제대로 이 값들을 추가를 시켜주지 못했다.

그러다 보니 답이 [1]에서 멈춰있었다. 

그래서 제대로 어떻게 코드가 처리되고 있는지를 알기 위해서 위에 주석 처리된 print문들을 찍게 되었고,

이를 직어보니 [1] [2] [3]과 같이 재귀를 돌 때 제대로 숫자는 리턴 하지만,

최종적으로 값들을 하나의 리스트에 저장하지 못했다는 점이 있었다.

따라서, 이를 해결하기 위해서, 재귀를 해서 리턴하는 값을 리스트에 넣는 코드로 수정이 필요했고,

이를 위해. extend()를 사용하게 되었다.

아직도 해당 코드를 보아도 제대로 이해를 했다고 보기는 어려운 것 같다.

다른 사람에게 설명하라고 하면 내가 제대로 설명을 하고 있는가에 대해서 스스로 의문을 가지고, 

설명하는 도중에도 왠지 막힐 것 같다는 생각이 든다.

따라서, 해당 문제는 계속 더 공부가 필요하다고 느낀다.

최근에 트리 이론과 재귀를 제대로 이해하고 이제 직접 코딩으로 구현을 해보는 연습을 하고 있는 중이다.

그 중에 내가 풀어놓고 답인지 아닌지 햇갈렸던 문제 중 하나가 위의 문제였다.

일단 답은 다음과 같이 간단하게(?) 구현이 가능하다.

# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        else:
            return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

일단 if not root 부분은 base 코드, 즉 재귀를 끝내기 위한 코드인 것은 금방 추론이 가능하다.

문제는 return 부분이다.

최대한 쉽게 말로 풀이를 해보자면 이렇게 된다.

1. 우선 3으로 root가 시작된다
2. 3의 root.left는 9가 된다.
3. self.maxDepth(root.left)에는 9가 들어가는 것이므로, maxDepth(self, 9)가 된다.
4. 9가 들어오면 일단 다시 else문으로 가게 된다.
5. 9일 때, self.maxDepth(root.left)와 self.maxDepth(root.right)는 둘 다 null이므로, return max(0, 0)+1이 되므로 return 1이 된다.
6. 따라서 이제 9일 때 1이 나오기 때문에 재귀한 것을 타고 올라가면, 맨 처음 root가 3이었을 때, max(1, self.maxDepth(root.right))+1인 것을 알 수 있다.
7. 이제 self.maxDepth(root.right)도 똑같이 해주면 (이 경우에는 20이 들어가고, 들어간 후 각각 15, 7이 나올 것이다)), 결국 root가 3이었을 때, return self.maxDepth(1,2)+1이 된다.
8. 따라서, 결론적으로는 return 2+1 즉, return 3이 나온다.

재귀는 계속 풀어봐야하는 것을 느낀다.

과거에 여러 번 코딩테스트 시도를 실패했던 첫 번째 관문 중 하나가 나에게는 항상 재귀였다 (이를 활용한 트리도...).

계속 여러 문제를 이번에는 끈덕지게 풀어보고자 한다.