# 144. Binary Tree Preorder Traversal

{% embed url="<https://leetcode.com/problems/binary-tree-preorder-traversal/>" %}

`DFS preorder`

一般都是 `recursively`比较快，这题大概是因为要传递`res`，比较下来竟然是`iteratively`快。

{% tabs %}
{% tab title="iteratively" %}

```python
# 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: TreeNode) -> List[int]:
        if not root: return []
        
        stack = collections.deque([root])
        res = []
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.right: stack.append(node.right)
            if node.left: stack.append(node.left)
            
        return res
```

{% endtab %}

{% tab title="recursively" %}

```python
# 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: TreeNode) -> List[int]:
        res = []
        
        def preorder(node, res):
            if not node: return
            res.append(node.val)
            preorder(node.left, res)
            preorder(node.right, res)
        
        preorder(root, res)
        
        return res
```

{% endtab %}
{% endtabs %}
