[LeetCode]Binary Tree Inorder Traversal

https://leetcode.com/problems/binary-tree-inorder-traversal/description/

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

        def inorder_traversal(root):
            if root and root.left:
                inorder_traversal(root.left)
            
            if root:
                output.append(root.val)

            if root and root.right:
                inorder_traversal(root.right)

        inorder_traversal(root)

        return output

접근 방법

1. 중위 순회를 위한 inorder_traversal 함수를 만듭니다.
2. 왼쪽에 자식 노드가 있다면 재귀 방식으로 왼쪽을 탐색하러 들어갑니다.
3. 방문한 노드를 기록합니다.
4. 오른쪽에 자식 노드가 있다면 재귀 방식으로 오른쪽을 탐색하러 들어갑니다.

트리를 순회하는 방법에는 전위, 중위, 후위 순회가 있습니다. 

전위 순회는 뿌리 -> 왼쪽 자식 -> 오른쪽 자식 순으로 노드를 방문합니다.

중위 순회는 왼쪽 자식 -> 뿌리 -> 오른쪽 자식 순으로 노드를 방문합니다.

후위 순회는 왼쪽 자식 -> 오른쪽 자식 -> 뿌리 순으로 노드를 방문합니다.

 

즉, 재귀를 통해 왼쪽의 노드를 모두 방문하도록 한 후에 방문을 기록하고 나머지 오른쪽 부분도 재귀로 방문하도록 합니다.

(ps. 재귀 방식을 이용하는 것, 방문한 노드를 기록하는 것을 중간에 위치시켜 중위 순회를 만드는 것, 함수를 따로 선언한 것이 포인트입니다.)

 

두번째로 시도한 답안

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

        def inorder_traversal(root):
            if not root:
                return

            inorder_traversal(root.left)
            # inorder traversal, so output append in middle
            output.append(root.val)
            inorder_traversal(root.right)

        inorder_traversal(root)

        return output

접근 방법

첫 번째와 방식은 동일하나 가독성을 조금 더 높인 코드입니다. root가 존재하지 않으면 early return 하여 불필요한 if clauses를 제거 했습니다.