[Binary Tree / 이진 트리] Leetcode - Binary Tree Preorder Traversal Python 파이썬

요즘에는 개발자들이 회사에 취업하기 위해서 사용한다는 리트코드 (leetcode) 사이트의 문제들을 풀어보고 있습니다. 이제 막 시작한 초보자라 힘든 점이 많아서 이렇게 글로 남겨서 복습하려고 합니다.

 

주제: Binary Tree - Traverse a Tree

문제: Binary Tree Preorder Traversal
등급: EASY

내용: "Given the root of a binary tree, return the preorder traversal of its nodes' values."
root 노드가 주어진 이진트리이다.

<코드>

내가 한 것은 recursive method이다. 도대체 iterative method으로 어떻게 풀지는 몰랐다. 솔직히 recursive도 이해 완전히 한 것은 아니다. 

class Solution(object):
    def preorderTraversal(self, root):
        ans = []
        if not root:
            return []
        
        ans.append(root.val)
        
        if root.left:
            ans += self.preorderTraversal(root.left)
            
        if root.right:
            ans += self.preorderTraversal(root.right)
        
        return ans

내가 이해한 논리로는,

 

우선 ans라는 list를 만든다. 다음 줄: 만약에 root가 비어있다면, 그대로 empty 리스트를 반환하도록 하자.

 

그 후, root의 첫 value를 집어넣는다. 그후, recursion이 일어나는 것은, if root.left와 root.right이다. 다시 한번 preorderTraversal(root)을 사용하면서 무조건 왼쪽 value를 먼저 넣게 되는 것이다 (ans.append(root.val)를 활용해서)

 

Iterative method은 무엇을 활용할지 몰라서 discussion을 확인해보았다.

 

stack's LIFO 메서드를 활용했다는 데 뭔 말인지는 몰라도 아주 잘 좋은 코드이다.

class Solution(object):
    def preorderTraversal(self, root):
        ans = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                ans.append(node.val)
                stack.append(node.right)
                stack.append(node.left)
                
        return ans

 

위의 코드와 똑같이 return할 empty list를 만들어준다. 그리고 우선 [첫 root]을 포함한 스택을 만들어준다. 스택이 비어있지 않다면 (= 탐색할 node가 있다면), node에 스택 끝에서 pop()을 통해 할당, 그 노드가 있다면, 우선 탐색한 ans 리스트에 넣는다.

 

그 후, 찾아보니 Stack's LIFO는 last in, first out이었다. 마지막에 들어간 것이, 먼저 나오는 것. 그래서, node.right, 오른쪽 노드를 먼저 넣고, 왼쪽 노드를 넣는다. 그래야지 while loop으로 다시 돌아갔을 때 왼쪽부터 살펴보게 될 것이다.

 

<오류, 힘들었던 점>

Recursion이나 iterative이나 내 머리에서 나올만한 것들이 아니다. 힘들긴 한데, 방법을 알아내니 재밌다.

 

<총평 외 comment>

 

Happy coding!