状态机过程详解

我们定义三个状态：

1. LEFT状态：代表左右子树均未被遍历

2. RIGHT状态：代表左子树被遍历

3. UP状态：代表左右子树都被遍历过

注意还需要一个栈用于存储遍历路径，方便拿取父节点。

• 实现了这个迭代过程后，我们发现，实际上LEFT状态就是前序遍历的操作状态，RIGHT状态就是中序遍历的操作状态，UP状态就是后序遍历的操作状态，自此用迭代实现了递归的完全模拟。

画出状态转移图

(前序遍历代码)代码

这里只展示前序遍历的代码，中序和后序也很简单，直接在对应的状态取数值即可。

验证代码可以到leetcode平台：https://leetcode.cn/problems/binary-tree-preorder-traversal/submissions