# 94. Binary Tree Inorder Traversal

### Leetcode

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

### 題目

Given the `root` of a binary tree, return *the inorder 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,3,2]
```

**Example 2:**

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

**Example 3:**

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

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

* **方法一**

Recursion

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

Runtime: 60 ms, faster than 95.03% of JavaScript online submissions for Binary Tree Inorder Traversal.

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

* **方法二**

Iteration

```
var inorderTraversal = function(root) {
    if (root === null) return [];
    
    const result = [];
    const stack = [];
    let curr = root;
    while (curr != null || stack.length) {
      // 一直往左邊找直到找到左子樹為 null
      while(curr != null) {
          stack.push(curr);
          curr = curr.left;
      }
      curr = stack.pop();
      result.push(curr.val);
      curr = curr.right;
    }
    
    return result;
};
```

Runtime: 96 ms, faster than 38.70% of JavaScript online submissions for Binary Tree Inorder Traversal.

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

* **方法三**

Morris method

```
var inorderTraversal = function(root) {
    if (root === null) return [];
    
    const result = [];
    let curr = root;
    let prev;
    while (curr != null) {
      if(curr.left === null) {
          result.push(curr.val);
          curr = curr.right;
      } else {
          prev = curr.left;
          // 找出左子樹最右邊的節點
          while(prev.right !== null) {
              prev = prev.right;
          }
          // 將 curr 接在左子樹最右邊節點的右邊
          prev.right = curr;
          const temp = curr;
          // 樹根改為左子樹
          curr = curr.left;
          // curr 在接完後，原本的左子樹要清空
          temp.left = null;
      }
    }
    
    return result;
};
```

Runtime: 73 ms, faster than 71.57% of JavaScript online submissions for Binary Tree Inorder Traversal.

Memory Usage: 42 MB, less than 44.91% of JavaScript online submissions for Binary Tree Inorder Traversal.

### 參考資料

<https://www.cnblogs.com/anniekim/archive/2013/06/15/morristraversal.html>
