LeetCode: Binary Tree Inorder Traversal

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

 

Example 1:

Input: root = [1,null,2,3]

Output: [1,3,2]

Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output: [4,2,6,5,7,1,3,9,8]

Explanation:

Example 3:

Input: root = []

Output: []

Example 4:

Input: root = [1]

Output: [1]

 

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

 

Follow up: Recursive solution is trivial, could you do it iteratively?

 

 

이 문제는 dfs를 사용하여 중위 순위를 구현하는 방법이다.

 

초반에 root라고 주어진 데이터의 형식이 트리 형태가 아니라 list형식이라고 오해하여 트리를 처음부터 만드는 코드를

작성할 뻔 했지만 그게 아니라 미리 만들어져 있는 트리에서 중위 순위만 list로 출력하는 문제였다. 

 

중위순위란 부모의 left 부모 right 순으로 출력하는 것을 말한다. 

 

예를 들어 

 

작동 순서는 다음과 같다. 

• 1의 왼쪽은 null이므로 출럭 x
• 부모 = 1 이므로 출력
• 1의 오른쪽으로 이동
• 2의 왼쪽노드 3이 있으므로 3 출력 
• 부모 2 이므로 2 출력 
• 2의 오른쪽은 없으므로 끝

 

구현 방법은 정말 간단하다. 

 

미리 트리가 구성되어 있기 때문에 트리 탐색 코드를 recursive하게 짜면 된다. 

 

왼쪽을 미리 방문하므로 코드의 순서는

 

dfs(node.left)

results.append(node.val)

dfs(node.right)

 

순이 될 것이다!

 

 

 

---

구현 코드

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        
        results = []

        def dfs(node):
            if not node:
                return 
            
            dfs(node.left)
            results.append(node.val)
            dfs(node.right)

        dfs(root)

        return results