LeetCode 144(Binary Tree Preorder Traversal, Python)

1. 문제 링크

• https://leetcode.com/problems/binary-tree-preorder-traversal/

Binary Tree Preorder Traversal - LeetCode

 

2. 문제 설명

• 이진 트리의 root가 주어졌을 때, node value의 preorder traversal을 반환
  • 여기서 preorder traversal이란 부모 → 왼쪽 서브 트리 → 오른쪽 서브트리 순으로 탐색하는 것 
• 결국 이전에 풀었던 inorder traversal과 순서만 바뀐 형태
  •  https://codingbubu.tistory.com/26

3. 처음 풀이

• 부모 → 왼쪽 서브 트리 → 오른쪽 서브트리 순으로 탐색하는 것으로 
  • root value를 먼저 append 한 후, 왼쪽 서브 트리에 대한 재귀, 오른쪽 서브 트리에 대한 재귀를 하여 최종 결과값 반환

# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        if root is None:
            return result
        else:
            result.append(root.val)
            result += self.preorderTraversal(root.left)
            result += self.preorderTraversal(root.right)
        return result

4. 다른 풀이

• 거의 동일하나 아래처럼 한줄로 짜는 것도 가능. 

# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root :
            return []
        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)