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

2023. 8. 7. 21:17·Coding Practice/LeetCode
728x90

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

📖Problem : 94. Binary Tree Inorder Traversal

 

Binary Tree Inorder Traversal - LeetCode

Can you solve this real interview question? Binary Tree Inorder Traversal - Given the root of a binary tree, return the inorder traversal of its nodes' values.   Example 1: [https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg] Input: root = [1,nu

leetcode.com

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 문제라고 한다. 기본기를 탄탄히 하자!
728x90
저작자표시 비영리 변경금지 (새창열림)
'Coding Practice/LeetCode' 카테고리의 다른 글
  • [LeetCode] #101. Symmetric Tree (Python/파이썬)
  • [LeetCode] #70. Climbing Stairs (Python/파이썬)
  • [LeetCode] #15. 3Sum (Python/파이썬)
  • [LeetCode] #167. Two Sum 2 (Python)
밍구링구리
밍구링구리
밍구리의 실험실 이것저것 배우고 기록을 남깁니다
  • 밍구링구리
    Mingguri Labatory
    밍구링구리
    • 홈
    • 태그
    • 방명록
    • 깃허브
  • 전체
    오늘
    어제
    • 분류 전체보기 (92) N
      • Language & Framework (15)
        • Java (3)
        • Vue.js (1)
        • Spring Boot (10)
      • Computer Science (4)
        • Operating System) (0)
        • Database (2)
        • Network (1)
        • Data Structure (0)
        • Algorithm (1)
      • Architecture & Design (7)
      • Cloud & Infra (5)
      • Trouble Shooting (0)
        • 에러 해결 (0)
        • 삽질 기록 (0)
      • 회고 (0)
      • Coding Practice (38) N
        • Backjoon (20) N
        • LeetCode (6)
        • Programmers (12)
      • Book (0)
      • ETC (21)
        • 블로그 관리 (3)
        • 일상 (1)
        • 후기 (2)
        • 밍구의 실험실 (1)
        • 🤔Study . Question🔍 (14)
      • 부트캠프 (1)
  • 인기 글

  • 최근 글

  • 최근 댓글

  • 태그

    OOP
    골드5
    백엔드
    스케일아웃
    백준
    스케일업
    유스케이스
    프로그래머스
    투포인터
    SOLID
    객체지향
    퀴즈
    골드4
    구현
    우선순위큐
    그리디
    백트래킹
    git
    스터디
    level 2
    테스트케이스
    BFS
    Spring Boot
    코드잇
    LeetCode
    코딩테스트
    문제
    dfs
    vue.js
    알고리즘
  • 250x250
  • hELLO· Designed By정상우.v4.10.3
밍구링구리
[LeetCode] 94. Binary Tree Inorder Traversal (Python)
상단으로

티스토리툴바