94. Binary Tree Inorder Traversal

Inorder Traversal (중위 순회) : L - ROOT - R

Solution

재귀 함수를 사용해서 풀었다.

1. 왼쪽 노드를 방문한다.
2. 배열에 현재 노드의 값을 저장한다.
3. 오른쪽 노드를 방문한다.

# 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]:
        ans =[]

        def foo(cur):
            if cur.left is not None: foo(cur.left) # 왼쪽 노드
            ans.append(cur.val) # 배열에 저장
            if cur.right is not None: foo(cur.right) # 오른쪽 노드
        
        if root is not None:
            foo(root)
        
        return ans

시간 복잡도

결국은 모든 노드를 방문하므로 O(n)가 된다.