二叉树中序非递归遍历

Question

非递归中序遍历二叉树的步骤如下：

1. 初始化一个栈和一个指针，指针指向二叉树的根节点。
2. 当栈不为空或指针非空时，执行以下操作：
3. 如果指针非空，则将指针入栈，并将指针指向它的左子节点。
4. 如果指针为空，则取出栈顶元素，输出它的值，并将指针指向它的右子节点。

下面是 Python 代码实现：

def in_order_traversal(root):
    if not root:
        return
    stack = []
    cur = root
    while stack or cur:
        if cur:
            stack.append(cur)
            cur = cur.left
        else:
            cur = stack.pop()
            print(cur.val)
            cur = cur.right