## Tree - 94. Binary Tree Inorder Traversal

Updated on with 0 views and 0 comments

94. Binary Tree Inorder Traversal

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

Example:

Input: [1,null,2,3]
1

2
/
3
Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

go ：

``````/**

* Definition for a binary tree node.

* type TreeNode struct {

*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
// recursive
/*func inorderTraversal(root *TreeNode) []int {
var res []int

recursive(root, &res)

return res
}

func recursive(root * TreeNode, res *[]int) {
if root == nil {
return
}

recursive(root.Left, res)
*res = append(*res, root.Val)
recursive(root.Right, res)
}
*/

// iteratively
func inorderTraversal(root *TreeNode) []int {

var res []int
var stack []*TreeNode

cur := root
for cur != nil || len(stack) != 0 {
for cur != nil {
stack = append(stack, cur)
cur = cur.Left
}

// 走到最左
cur = stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
res= append(res, cur.Val)
cur = cur.Right
}

return res
}
``````