리트코드 94. Binary Tree Inorder Traversal

25 Nov 2022 in Algorithm

이진 트리의 순회(inorder traversal) 리스트를 반환하시오!

Tree 문제… 🎋

문제

94. Binary Tree Inorder Traversal 문제 링크

이진 트리의 순회(inorder traversal) 해보아라!

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

---

🤔 order 방식 중 inorder는?
LEFT → NODE → RIGHT

위의 그림의 노드를 inorder 순서로 진행하면? [1, 2, 3, 4, 5]가 됩니다.
(✨ All DFS traversals (preorder, inorder, postorder) in Python in 1 line 해당 글을 참고했습니다.)

왼쪽의 가장 깊은 노드 부터 inorder 순서로 리스트로 만들면 끝!

✅ 최종 Solution

def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
  def inorderDfs(node):
    if not node: return
    if node.left:
      inorderDfs(node.left)
    path.append(node.val)
    if node.right:
      inorderDfs(node.right)

  path = []
  inorderDfs(root)
  return path

dfs를 활용하여 재귀로 간단하게 풀 수 있었습니다.
inorder 순서대로 dfs 내에서 왼쪽 가장 깊이 들어간 후에 Node, Right 순서대로 진행하게 됩니다!