[leetcode] 144. Binary Tree Preorder Traversal Python

 

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

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()를 사용하게 되었다.

 

---

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

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

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

 

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