[leetcode] 144. Binary Tree Preorder Traversal

원문)

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

번역)

이진트리를 주어졌을때 그 노드값을 preorder 순회를 반환하라.


예제)

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

문제접근)

부모 -> 왼쪽 자식 -> 오른쪽 자식


코드)

1.  top-down

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: #top-down def preorderTraversal(self, root: TreeNode) -> List[int]: answer = [] self.top_down(root, answer) return answer def top_down(self, root: TreeNode, answer: List[int]): if root is None: return answer.append(root.val) self.top_down(root.left, answer) self.top_down(root.right, answer)

2. bottom-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # bottom-up def preorderTraversal(self, root: TreeNode) -> List[int]: answer = [] cur = [root] while cur: cn = cur.pop() if cn: answer.append(cn.val) cur.append(cn.right) cur.append(cn.left) return answer