[LeetCode]94.Binary Tree Inorder Traversal(Python)

📌 Problem (https://leetcode.com/problems/binary-tree-inorder-traversal/)

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

= 이진트리가 주어졌을 때, 각 노드의 값을 Inorder에 따라 배열하는 함수를 작성하시오.

 

📌 Example

📌 Inorder Traversal ?

출처 : https://zhang-xiao-mu.blog/2019/01/20/tree-traversal-preorder-postorder/

Tree 탐색 알고리즘 중 하나로 탐색 순서에 따라 종류가 나뉜다. 

• Postorder : 아래 > 위 / 왼쪽 노드 > 오른쪽 노드
• Preorder : 위 > 아래 / 왼쪽 노드 > 오른쪽 노드 
• Inorder : 왼쪽 노드 > 루트 (중앙 노드) > 오른쪽 노드 

아래의 구체적인 예시를 통해 이를 익혀보자. 

출처 : https://prepinsta.com/data-structures-algorithms/inorder-postorder-preorder-examples/

위의 트리를 보고 Preorder, Postorder, Inorder에 따른 탐색 노드의 순서를 살펴보자.

• Preorder : 위 > 아래 / 왼쪽 > 오른쪽 으로 진행되기 때문에 가장 위 쪽의 노드인 A부터 시작해서 아래의 노드 중 가장 오른쪽에 위치한 C에서 끝난다. 
• Postorder : 아래 > 위 / 왼쪽 > 오른쪽 으로 진행되어 가장 아래쪽의 왼쪽 노드인 D부터 시작해 같은 계층에 위치한 오른쪽 노드인 E를 탐색하면서 가장 위쪽의 노드인 A에서 끝나게 된다.
• Inorder : 왼쪽 > 중앙(root) > 오른쪽 으로 진행되고, 가장 아래쪽의 왼쪽 노드인 D에서 시작하지만 PostOrder와 달리 오른쪽 노드로 가지 않고, 중앙 노드(root)인 B를 탐색한다. 

 

노드를 탐색하는 방식을 토대로 위 문제를 풀어보자. 

 

📌 Solution

• DFS 유형의 문제를 푸는 방식에는 총 2가지가 있다.
  • 재귀함수
  • stack
• 필자는 재귀함수를 사용하여 풀어보았다. 

# 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: TreeNode) -> List[int]:
            if root is None: return []
            def dfs(root,res):
                if root is None: return
                dfs(root.left,res)
                res.append(root.val)
                dfs(root.right,res)
                return res
            return dfs(root,[])

• root의 print 해보면 아래와 같이 나온다. 

TreeNode{val: 1, left: None, right: TreeNode{val: 2, 
left: TreeNode{val: 3, left: None, right: None}, right: None}}

• 이를 보고 root의 요소를 하나씩 집어넣으면서 탐색하고 
• 해당 노드와 연결된 또 다른 tree 들의 노드가 있다면 탐색하지만
• 노드가 없을 경우에 함수를 탈출하여 return 하게 된다 .

 

아래의 방법은 stack으로 푼 코드이다. 

def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack = [root]
        res = []
        while stack:
            node = stack.pop()
            if node:
                stack.append(node.right)
                stack.append(node)
                stack.append(node.left)
            else:
                if stack:
                    node = stack.pop()
                    res.append(node.val)

• stack 은 재귀함수와 유사하게 각각의 노드에 딸린 트리를 호출하고,
• 각각의 트리에 담긴 값이 none일 경우 리스트에 append 한 다음에
• pop()하여 제거시킨다. 
• 이 과정을 반복하여 result의 값을 append 시킨다. 

---

dfs 문제의 기본에 충실할 수 있었던 문제 같다. 

easy여도 무시하면 안됨 !