0094.二叉树的中序遍历

https://leetcode.cn/problems/binary-tree-inorder-traversal/

方法一：迭代法

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。


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