# 144. Binary Tree Preorder Traversal

### Leetcode

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

### 題目

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

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg)

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

**Example 2:**

```
Input: root = []
Output: []
```

**Example 3:**

```
Input: root = [1]
Output: [1]
```

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

Recursion

```
var preorderTraversal = function(root) {
    if (root === null) return [];
    
    const result = [];
    const preOrder = (node) => {
        if (node) {
            result.push(node.val);
            preOrder(node.left);
            preOrder(node.right);
        }
    }
    preOrder(root);
    return result;
};
```

Runtime: 118 ms, faster than 14.86% of JavaScript online submissions for Binary Tree Preorder Traversal.

Memory Usage: 42.2 MB, less than 37.80% of JavaScript online submissions for Binary Tree Preorder Traversal.

* **方法二**

Iterations

利用 stack 紀錄遍歷所有節點

```
var preorderTraversal = function(root) {
    if (root === null) return [];
    
    const result = [];
    const stack = [root];
    while (stack.length) {
        const node = stack.pop();
        result.push(node.val);
        if (node.right) {
          stack.push(node.right);  
        }
        if (node.left) {
          stack.push(node.left);
        }
    }
    return result;
};
```

Runtime: 74 ms, faster than 71.22% of JavaScript online submissions for Binary Tree Preorder Traversal.

Memory Usage: 42.4 MB, less than 17.29% of JavaScript online submissions for Binary Tree Preorder Traversal.
