[LeetCode] 94. Binary Tree Inorder Traversal (Python)

작성일시: 2023년 8월 4일 오후 2:10
등급: Easy

📖Problem : 94. Binary Tree Inorder Traversal

Binary Tree Inorder Traversal - LeetCode

Given the root of a binary tree, return *the inorder traversal of its nodes' values*.
⇒ 이진 트리가 주어졌을 때, 각각의 노드를 inorder trabersal 순서에 따라 배열하는 함수를 작성하라!

Example1:

Input: root = [1,null,2,3]
Output: [1,3,2]

 

 

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• 100 <= Node.val <= 100

🔍Institution

여기서 Inorder Traversal이란?
자료구조에 대해 공부했다면 당연히 알고 있는 지식이겠지만 이미지로 한번 더 살펴보자!

 

그렇다면 이 문제는 DFS일까, BFS일까?

• 여기서 BFS는 left에서 right로 가지만 DFS는 깊게 들어가는 것이다.
• DFS를 탐색하는 방식으로는 postorder, inorder, preorder가 있다. 그 중에서도 inorder로 traversal을 하라고 하였으므로, DFS로 푸는 문제이다.

 

DFS는 어떻게?

• DFS는 스택이나 재귀함수로 푼다.

 

여기서 어떤 과정이 반복될까?

• left, root, right순으로 호출하는 것이 반복된다.

이때 leetcode에서는 Tree code를 아래와 같이 제공한다. 따라서 입력받거나 tree의 로직을 짤 필요는 없다.

 

🔍Process

1. 재귀함수 호출방식

inorder의 방식은 left, root, right이다. 따라서 재귀함수로 left, root, right순으로 호출하면 되겠다고 판단하였다.

def dfs(root):
    dfs(root.left)
    dfs(root.val)
    dfs(root.right)

이때 반환값이 있어야 한다. 반환된 output을 보면 리스트 형태이기 때문에 answer 리스트를 만들어준 후, 호출할 때 answer를 append해준다.

2. return 해줄 정답 리스트, answer

answer = []

이때 어떤 값을 answer해줘야 할까?

print(root) 하면 아래와 같이 나온다.

 

3. 문제에서 주어준 TreeNode 방식 이해하기 ➡ answer에 저장해야 할 값 찾기

print(root)

 

TreeNode{val: 1, left: None, right: TreeNode{val: 2, left: TreeNode{val: 3, left: None, right: None}, right: None}}

⇒ 이를 통해 보았을 때 answer 리스트에 저장해야 하는 값은 val이라는 것을 알 수 있다.

left인 줄 알았던 나.. 역시 직접 적어봐야 정확한 값을 알 수 있다. 어쨌든, answer리스트에는 val의 값을 append하면 된다. val이 끝이니까 dfs함수로 호출할 필요는 없다. 따라서 이렇게 표현할 수 있다.

    answer = []
    def dfs(root):
        dfs(root.left)
        answer.append(root.val) #answer 리스트에 추가
        dfs(root.right)

    dfs(root)
return answer

 

4. 재귀함수 종료 조건

이때 여기서 끝날 수 없다. 재귀함수를 종료할 조건이 필요하며, example2([]) 처럼 빈 리스트가 들어올 경우 빈 리스트가 return되도록 해야 한다.
즉, root에 아무 값도 없을 경우를 고려해야 한다. root에 아무값이 없다면 더 진행할 필요 없이 그냥 pass하면 된다.

    answer = []
    def dfs(root):
        if root is None:
            continue
        else:
            dfs(root.left)
            answer.append(root.val)
            dfs(root.right)
    dfs(root)
return answer

여기서 혹시 잘못된 것을 눈치챘는가?!
continue를 사용하면 아래와 같은 에러가 발생한다.

continue는 loop에서는 적절하지 않은 방식이다. 난 바보같이 몰랐다.. 이렇게 배워가는거지 뭐..
loop (재귀든 뭐든)일 때 continue와 같은 역할을 하는 것은 return이다. 그냥 return만 적어주면 된다. 이렇게 배운다.
따라서 아래와 같은 최종 코드가 나올 수 있따.

# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        answer = []
        print(root)
        def dfs(root):
            if root is None:
                return
            else:
                                # inorder
                dfs(root.left) #
                answer.append(root.val)
                dfs(root.right)

        dfs(root)
        return answer

---

🔍Answer

🚩My submission

# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        answer = []
        print(root)
        def dfs(root):
            if root is None:
                return
            else:
                dfs(root.left)
                answer.append(root.val)
                dfs(root.right)

        dfs(root)
        return answer

🚩Others submission

나처럼 풀이해도 되지만, 아래의 코드도 깔끔해서 가져왔다.

def inorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None: return []
        def dfs(root,res):
            if root is None: return
            dfs(root.left,res)
            res.append(root.val)
            dfs(root.right,res)
            return res
        return dfs(root,[])

DFS를 푸는 방법은 스택과 재귀함수 이렇게 2가지가 있으며, 내가 풀지 않은 스택으로 푸는 방법의 풀이를 가져왔다.

def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack = [root]
        res = []
        while stack:
            node = stack.pop()
            if node:
                stack.append(node.right)
                stack.append(node)
                stack.append(node.left)
            else:
                if stack:
                    node = stack.pop()
                    res.append(node.val)

---

💡TIL

• 함수에서 나올라면 continue가 아니라 return… 을 해야 한다.
• 재귀함수에 대해 거부감이 들지만 코드로 구현하는 것은 재귀가 더 쉽다.
• 이 문제는 DFS의 기본이 되는 traversal 문제라고 한다. 기본기를 탄탄히 하자!