Leetcode - Binary Tree Postorder Traversal(후위 순회) Python 파이썬

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

 

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

문제: Binary Tree Postorder Traversal
등급: EASY

본문 내용과 무관합니다.

<코드>

너무나도 많이 고민했다. 어제 적은 코드에서 무엇을 바꾸면, root를 자연스럽게 마지막에 더할수 있을까? 고민했다. (어제 2번 코드 참고)

 

처음에 들은 생각은, while loop에 if 식을 하나 넣으면 되지 않을까 생각했다. 이 방식은 되지 않았다. if를 넣는다면, 무슨 if를 넣어야 할지 몰랐다. 바로 든 생각은, stack len()가 1일 경우, append를 안하면 되지 않을까 생각했는데, 당연히 안되었다. 그 후, if curr == root를 해볼까 생각했는데, 그럼 while loop이 끝나지 않을 것이다.

 

또는, 왼쪽부터 하고, 그 다음 오른쪽을 더한 후 마지막 root을 더하면 되지 않을까 생각했다. 그런데, 이 방식은 너무나도 깔끔하지 못하다.

 

그래서, 오늘도 discussion을 살펴보았다. 두 가지 솔루션 아이디어를 얻었다.

 

1번: stack 리스트에 set()를 활용하는 방법.

2번: right 먼저하는 preordertraversal를 한 후, reverse하는 방법.

우선 두번째 방법의 코드부터:

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

왼쪽을 먼저 살펴보는 대신, 오른쪽을 먼저 살펴서 preordertraversal의 반대 방법으로 우선 while loop을 구성해줍니다. 그 후, [::-1]으로 뒤집어주기만 하면 끝!

 

1번 방법은, 참으로 기발하다고 느낀 코드였다. 어떻게 이런 생각을... 할 수 있었을까? 속도는 비슷하지만, 메모리를 아낀다는 결과가 나왔는데, 이건 약간 이해하기 어려웠다. 

 

어쨌든, 코드는:

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

set의 list로 stack을 만듬으로써, 그 node에 "방문"했는지 안했는지의 확인이 가능해졌다. 처음에는 False 상태로 들어가있고, 하나씩 왼쪽부터 "방문"하면서 true로 바꾸고 그 값을 결과, ans 리스트로 넣는다.

 

첫번째 root node를 두 번 방문한다는 약간의 번거로움(?)이 있지만 꽤나 괜찮은 방법이라고 생각된다.

 

<총평>

이렇게 세가지 순회 방법을 살펴보게 되었다.

 

Happy coding!