트리 이론을 공부한 후 가장 처음으로 건드려보려고 한 문제가 바로 이 문제다.
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()를 사용하게 되었다.
아직도 해당 코드를 보아도 제대로 이해를 했다고 보기는 어려운 것 같다.
다른 사람에게 설명하라고 하면 내가 제대로 설명을 하고 있는가에 대해서 스스로 의문을 가지고,
설명하는 도중에도 왠지 막힐 것 같다는 생각이 든다.
따라서, 해당 문제는 계속 더 공부가 필요하다고 느낀다.
'Leetcode' 카테고리의 다른 글
| [leetcode] 104. Maximum Depth of Binary Tree Python (0) | 2022.05.07 |
|---|---|
| [leetcode] 1464. Maximum Product of Two Elements in an Array Python (0) | 2022.04.07 |
| [leetcode] 643. Maximum Average Subarray I Python (0) | 2022.04.07 |
