Contents

# 94. Binary Tree Inorder Traversal

## 題目 :

Given the root of a binary tree, return the inorder traversal of its nodes' values.

### Example :

Note

Example 1:

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

Example 2:

Input: root = [] Output: []

Example 3:

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

Example 4:

Input: root = [1,2] Output: [2,1]

Example 5:

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

#### 解題思路 :

• 這題需要我們做inorder traversal 作法與preorder類似，可以參考 leetcode144題解

• inorder visit順序 : left -> root -> right

• 所以不管在哪個子樹，一開始都要直接走到最左邊

• 做binary tree traversal可以用recursive or Iterative(Stack)

### Recursive解法

• time complexity: O(n) , space complexity: O(n)

Runtime: 0 ms, faster than 100.00% of Go online submissions for Binary Tree Inorder Traversal.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 `````` ``````func inorderTraversal(root *TreeNode) []int { var res []int var inorder func(node *TreeNode) inorder = func(node *TreeNode) { if node == nil { return } inorder(node.Left) res = append(res, node.Val) inorder(node.Right) } inorder(root) return res } ``````

### Iterative(Stack)解法

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 `````` ``````func inorderTraversal(root *TreeNode) []int { var res []int var stack []*TreeNode if root == nil { return res } visited := root stack = append(stack, visited) for visited.Left != nil { stack = append(stack, visited.Left) visited = visited.Left } for len(stack) != 0 { visited = stack[len(stack)-1] stack = stack[:len(stack)-1] res = append(res, visited.Val) if visited.Right != nil { stack = append(stack, visited.Right) visited = visited.Right for visited.Left != nil { stack = append(stack, visited.Left) visited = visited.Left } } } return res } ``````