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

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

 

어제 Binary Search와 이어집니다.

2022.01.16 - [코딩 공부] - [Binary Tree / 이진트리] Leetcode - Binary Tree Preorder Traversal Python 파이썬

문제: Binary Tree Inorder Traversal 
등급: EASY (분명 easy인데... easy인데..!!)

내용: "Given the root of a binary tree, return the inorder traversal of its nodes' values."

<코드>

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

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

 

recursion이 일어나는 것은, if root.left와 root.right이다. 다시 한번 preorderTraversal(root)을 사용하면서 무조건 왼쪽 value를 먼저 넣게 되는 것이다 (ans.append(root.val)를 활용해서) 어제 적은 코드와 다른 점은 root.left recursion 뒤, root.val를 중간에 넣게 되었다는 점이다.

 

iterative로 한 번 풀어보려고 했다. 그런데, 무엇을 해야할지는 잘 모르겠다. 그래서, solution을 보았다! 그런데 solution은 언제나 java로 적혀있어서 이해하는데 시간이 조금 많이 걸렸다.

class Solution(object):
    def inorderTraversal(self, root):
        ans = []
        stack = []
        
        curr = root
        while stack or curr:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            ans.append(curr.val)
            curr = curr.right
        
        return ans

자, 한 번 살펴보자. ans 리스트를 만든 것은 recursive와 같다. 그리고, 스택을 만들었다. 스택은 앞으로 볼 node를 저장해놓는다고 생각하면 된다. 'LIFO', 마지막으로 들어간 것이 처음으로 나온다는 것만 기억하면서 사용하자.

current = root로 설정한다. while stack or curr로 모든 node를 살펴보게 하며, while curr 루프로 항상 왼쪽 노드부터 더하게 하자. 만약 왼쪽 노드가 없다면, 마지막 왼쪽 노드를 pop()해서 append를 통해 넣은 후, 마지막 왼쪽 노드 전 노드의 오른쪽 가서 왼쪽 노드들을 찾아본다. 

 

그렇게 iteration이 되다보면, inordertraversal 정리가 돼있을 것이다 (참고로 inorder는 왼쪽, root, 오른쪽 노드로 정리).

<오류, 힘들었던 점>

아, DFS, BFS, 다 나에게 어려운 개념들. 언제쯤 잘 이해가 되려는지.

<총평>

Happy coding!

Binary Tree Inorder Traversal - LeetCode