# 145. Binary Tree Postorder Traversal

### Leetcode

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

### 題目

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

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/08/28/pre1.jpg)

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

**Example 2:**

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

**Example 3:**

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

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

* **方法一**

Recursion

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

Runtime: 92 ms, faster than 45.15% of JavaScript online submissions for Binary Tree Postorder Traversal.

Memory Usage: 42.3 MB, less than 30.59% of JavaScript online submissions for Binary Tree Postorder Traversal.

* **方法二**

Iteration

```
var postorderTraversal = function(root) {
    if(root === null) return [];
    
    const result = [];
    const stack = [root];
    while(stack.length) {
        const node = stack.pop();
        result.push(node.val);
        // 左邊先放入 stack 的，最後會是排序在前面的
        // postorder left -> right -> root
        // 這裡的 stack 反向放 root -> right -> left
        if (node.left) stack.push(node.left);
        if (node.right) stack.push(node.right);
    }
    
    // 倒轉過來
    return result.reverse();
};
```

Runtime: 106 ms, faster than 25.24% of JavaScript online submissions for Binary Tree Postorder Traversal.

Memory Usage: 42.1 MB, less than 38.09% of JavaScript online submissions for Binary Tree Postorder Traversal.

### 參考資料

<https://jstechroad.com/algorithms/leetcode-145-binary-tree-postorder-traversal-javascript/>
