参考力扣题解
作者：hzhu212
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
此思路复杂度低，且简洁易懂，对于前序、中序、后序遍历，能够写出完全一致的代码，只需要调整左右节点的入栈顺序即可。
（注：由于栈FIFO的特性，入栈顺序应与遍历顺序相反，如中序遍历为左、中、右，则入栈顺序为右、中、左。）
核心思想如下：
使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依 次入栈。
如果遇到的节点为灰色，则将节点的值输出。
public class 二叉树的中序遍历_94 {
class ColorNode {
TreeNode node;
String color;
public ColorNode(TreeNode node, String color) {
this.node = node;
this.color = color;
}
}
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<Integer>();
}
List<Integer> res = new ArrayList<>();
Stack<ColorNode> stack = new Stack<>();
stack.push(new ColorNode(root, "white"));
while (!stack.empty()) {
ColorNode cn = stack.pop();
if (cn.color.equals("white")) {
if (cn.node.right != null) {
stack.push(new ColorNode(cn.node.right, "white"));
}
stack.push(new ColorNode(cn.node, "gray"));
if (cn.node.left != null) {
stack.push(new ColorNode(cn.node.left, "white"));
}
} else {
res.add(cn.node.val);
}
}
return res;
}
}
