二叉树非递归遍历的实现

二叉树非递归遍历一般使用栈这种数据结构来实现。

1. 非递归前序遍历：

非递归前序遍历是先遍历根节点，然后左子树，最后右子树。

算法步骤：

1. 初始化栈stack，将根节点入栈。
2. 当栈不为空时，弹出栈顶元素cur，并输出cur的值。
3. 若cur的右子树不为空，则将右子树入栈。
4. 若cur的左子树不为空，则将左子树入栈。
5. 重复步骤2-4，直到栈为空。

代码实现：

def preorderTraversal(root):
    if not root:
        return []
    stack, res = [root], []
    while stack:
        cur = stack.pop()
        res.append(cur.val)
        if cur.right:
            stack.append(cur.right)
        if cur.left:
            stack.append(cur.left)
    return res

2. 非递归中序遍历：

非递归中序遍历是先遍历左子树，然后根节点，最后右子树。

算法步骤：

1. 初始化栈stack和指针cur，cur指向根节点。
2. 当栈不为空或cur不为None时，重复步骤3-5。
3. 若cur不为None，则将cur入栈，并将cur指向cur的左子树。
4. 若cur为None，则弹出栈顶元素top，并输出top的值，将cur指向top的右子树。
5. 重复步骤2-4，直到栈为空且cur为None。

代码实现：

def inorderTraversal(root):
    if not root:
        return []
    stack, cur, res = [], root, []
    while stack or cur:
        if cur:
            stack.append(cur)
            cur = cur.left
        else:
            top = stack.pop()
            res.append(top.val)
            cur = top.right
    return res

3. 非递归后序遍历：

非递归后序遍历是先遍历左子树，然后右子树，最后根节点。

算法步骤：

1. 初始化栈stack和指针cur，cur指向根节点。
2. 当栈不为空或cur不为None时，重复步骤3-5。
3. 若cur不为None，则将cur入栈，并将cur指向cur的左子树。
4. 若cur为None，则弹出栈顶元素top，并将top入另一个栈temp中。
5. 将cur指向top的右子树。
6. 重复步骤2-5，直到栈为空且cur为None。
7. 弹出temp中的元素，输出其值。

代码实现：

def postorderTraversal(root):
    if not root:
        return []
    stack, temp, res, cur = [], [], [], root
    while stack or cur:
        if cur:
            stack.append(cur)
            temp.append(cur)
            cur = cur.right
        else:
            top = stack.pop()
            cur = top.left
    while temp:
        res.append(temp.pop().val)
    return res