# 2022-06-30

## 94. Binary Tree Inorder Traversal

### Description

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• The number of nodes in the tree is in the range `[0, 100]`.

• `-100 <= Node.val <= 100`

### Solution

#### Approach #0: Recursive

``````/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func inorderTraversal(root *TreeNode) (ans []int) {
var dfs func(*TreeNode)
dfs = func(node *TreeNode) {
if node == nil {
return
}
dfs(node.Left)
ans = append(ans, node.Val)
dfs(node.Right)
}
dfs(root)
return
}``````

#### Approach #1: Iterative

``````/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func inorderTraversal(root *TreeNode) (ans []int) {
st := []*TreeNode{}
for root != nil || len(st) > 0 {
for root != nil {
st = append(st, root)
root = root.Left
}
root = st[len(st)-1]
st = st[:len(st)-1]
ans = append(ans, root.Val)
root = root.Right
}
return
}``````

Last updated