一个非递归算法写出先序遍历最后一个数

先序遍历的顺序是：根节点 -> 左子树 -> 右子树。

非递归的先序遍历算法可以使用栈来实现。算法流程如下：

1. 将根节点入栈；
2. 当栈不为空时，执行以下步骤：
- 弹出栈顶元素，输出该元素的值；
- 如果该元素有右子树，将右子树入栈；
- 如果该元素有左子树，将左子树入栈；
3. 当栈为空时，遍历结束。

最后一个数即为最后弹出的数，也就是最后一个出栈的数。

下面是一个示例代码实现：

def last_preorder(root):
    stack = [root]
    last = None
    while stack:
        node = stack.pop()
        if node:
            last = node.val
            stack.append(node.right)
            stack.append(node.left)
    return last

其中，`root` 是二叉树的根节点，`val` 是二叉树节点的值。`last` 变量用于记录最后一个输出的节点的值。

相关问题

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

可以使用 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

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

写一个非递归的先序遍历算法

非递归的先序遍历算法可以使用栈来实现。具体步骤如下：

1. 将根节点入栈
2. 循环执行以下步骤直到栈为空：
1. 弹出栈顶节点，访问该节点
2. 如果该节点有右子节点，则将右子节点入栈
3. 如果该节点有左子节点，则将左子节点入栈

以下是非递归先序遍历算法的示例代码（假设节点类为Node，其中包含左子节点和右子节点）：

void preOrderTraversal(Node root) {
    if (root == null) {
        return;
    }
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Node node = stack.pop();
        System.out.println(node.value); // 访问节点
        if (node.right != null) {
            stack.push(node.right); // 右子节点入栈
        }
        if (node.left != null) {
            stack.push(node.left); // 左子节点入栈
        }
    }
}