一个非递归算法写出二叉树先序遍历最后一个数不掉用栈

可以使用 Morris 遍历算法。该算法利用了线索二叉树的思想，将每个节点的右子树指向其后继节点，从而实现不需要使用栈的遍历。

具体实现步骤如下：

1. 将当前节点设为根节点。

2. 如果当前节点的左子树为空，则输出当前节点的值，并将其右子节点作为当前节点。

3. 如果当前节点的左子树不为空，在当前节点的左子树中找到当前节点在中序遍历中的前驱节点。

a. 如果前驱节点的右子节点为空，将它的右子节点设置为当前节点，当前节点更新为其左子节点。

b. 如果前驱节点的右子节点为当前节点，将它的右子节点重新设为空（恢复树的形状），输出当前节点的值，当前节点更新为其右子节点。

4. 重复步骤 2 和步骤 3，直到遍历完整棵树。

实现代码如下：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def morris_traversal(root: TreeNode) -> list:
    res = []
    curr = root
    while curr:
        if curr.left is None:
            res.append(curr.val)
            curr = curr.right
        else:
            # 找到当前节点的前驱节点
            pre = curr.left
            while pre.right and pre.right != curr:
                pre = pre.right
            if pre.right is None:
                # 将前驱节点的右子节点指向当前节点，以便后续恢复树的形状
                pre.right = curr
                curr = curr.left
            else:
                # 恢复树的形状，输出当前节点的值，当前节点更新为其右子节点
                pre.right = None
                res.append(curr.val)
                curr = curr.right
    return res

注意：这种算法会改变树的形状，因此不适用于需要多次遍历的情况。另外，由于需要修改树的结构，所以该算法不是完全不使用栈，而是用了隐式的栈（即树的右子节点）。