[LEETCODE] 94: Binary Tree Inorder Traversal(Python)

Binary Tree Inorder Traversal - LeetCode

문제 설명

이진 트리의 루트가 주어졌을 때 해당 노드들을 중위 순회로 반환해 보자.

나의 풀이

입력은 다음과 같이 주어진다.

# 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]:

중위 순회는 왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드 순으로 순회하는 방식이다. 재귀를 통해 구현할 수 있다.

1. 현재 노드가 None이라면 그대로 재귀를 끝낸다(return).
2. left를 현재 노드로 설정하는 함수를 재귀 호출한다.
3. left를 전부 확인했다면 현재 노드 val을 arr에 삽입한다.
4. right를 현재 노드로 설정하는 함수를 재귀 호출한다.
5. 재귀가 전부 종료되었다면 arr을 반환한다.

# 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]:
        def func(root):
            if root==None:
                return
            func(root.left)
            arr.append(root.val)
            func(root.right)
        arr=[]
        func(root)
        return arr

시간복잡도

노드의 개수만큼 순회하므로 O(n)이다.