# 94. Binary Tree Inorder Traversal

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

### 1. iterative

若 cur 不為 null

一路走左, 更新 cur 為左

到底了 => pop(), 塞值,&#x20;

檢查右邊有無元素

有: 又一路走左

無: pop() 塞值

反覆...

O(n), O(n)

```java

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        
        Stack<TreeNode> stack = new Stack<>();
        
        TreeNode cur = root;
        
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            res.add(cur.val);
            cur = cur.right;
        }
        return res;
    }
}

```

or like this

只有外面有 while, 好像比較合理, 概念一樣

```java
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                res.add(root.val);
                root = root.right;  
            }
        }
        return res;
    }

}
```

### 2. recursion

時間複雜度：O （n ）。

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-M8K1MWT7F9GhsFRlESL%2F-M8K3z-zXF366MULq53-%2Fimage.png?alt=media\&token=f5e2678c-9632-4966-b01e-d94d2b39f4c1)

空間複雜度：最壞情況下需要空間上O （n ），平均情況為O（ log n）。

## this is more clean

```java
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }
    private void helper (TreeNode root, List<Integer> res) {
        if (root == null) return;
        helper(root.left, res);
        res.add(root.val);
        helper(root.right, res);
    }
}
```