94. Binary Tree Inorder Traversal (leetcode Python) +DFS로 풀기

학부에서 공부했던 Binary Tree에서 lnorder 형식으로 탐색하는 문제가 나왔습니다.

문제:

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

Example

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

tree의 입력값을 받으면 inorder탐색을 하여 경로를 반환하는 문제입니다. 저는 문제를 보고 DFS로 풀면 좋겠다고 생각했습니다.

# 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]:
        reuslt = []
        
        def dfs(node):
            if node is not None:
                dfs(node.left)
                reuslt.append(node.val)
                dfs(node.right)
            
        dfs(root)
        return reuslt

빈 배열을 하나 선언해줍니다. 그러고 dfs함수를 만들어줍니다. 이때 왼쪽 탐색하고 값을 result에 대입하고 오른쪽 탐색하고 node가 None이 아닐 때까지 순회를 해줍니다. 만약 다른 inorder방식이아니라 Preorder나 Postorder라면 알맞게 탐색 순서를 바꾸면 됩니다.