# LeetCode – 94. Binary Tree Inorder Traversal

## Recursive version

func inorderTraversal(_ root: TreeNode?) -> [Int] {
var arr = [Int]()
inorderHelper(root , &arr)
return arr
}

func inorderHelper(_ root: TreeNode?, _ arr: inout [Int]) {
guard let root = root else { return }
inorderHelper(root.left, &arr)
arr.append(root.val)
inorderHelper(root.right, &arr)
}

## 法ㄧ:

func inorderTraversal(_ root: TreeNode?) -> [Int] {
if root == nil { return [] }
var arr: [Int] = []
var cur: TreeNode? = root
var stack: [TreeNode?] = []
stack.append(root)

while !stack.isEmpty {
while cur?.left != nil {
stack.append(cur?.left)
cur = cur?.left
}
if let node = stack.removeLast() {
arr.append(node.val)
cur = node.right
stack.append(node.right)
}
}
return arr
}

## 法二:

func inorderTraversal(_ root: TreeNode?) -> [Int] {
guard let root = root else { return [] }
var arr = [Int]()
var cur: TreeNode? = root
var stack: [TreeNode] = [root]
while !stack.isEmpty {
if let left = cur?.left {
stack.append(left)
cur = cur?.left
} else {
let n = stack.removeLast()
arr.append(n.val)
if let right = n.right {
stack.append(right)
cur = right
}
}
}
return  arr
}