LeetCode: Binary Tree Preorder Traversal

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

 

Example 1:

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

Output: [1,2,3]

Explanation:

Example 2:

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

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

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?

 

이 문제는 트리의 전위 순회를 구현하는 문제이다. 

 

탐색하는 Tree에 대해서 value를 출력한 후에 재귀적으로 왼쪽부터 트리의 자식노드를 방문하도록 만들면 되는 문제이다. 

 

구현은 생각보다 쉽다.

 

root가 None이라면 빈 list를 반환해주고, init을 사용하여 self.res = [] 라는 결과를 반환하는 list를 만들어주었다.

 

이후에 전위순회 과정을 하여 res에 각 tree의 value를 append 해주면 된다.

 

순서는 다음과 같다.

 

self.res.append(root.val)

self.preorderTraversal(root.left)
self.preorderTraversal(root.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 __init__(self):
        self.res = []

    def preorderTraversal(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        if root is None:
            return []

        self.res.append(root.val)
        self.preorderTraversal(root.left)
        self.preorderTraversal(root.right)

        return self.res