二叉树的先序非递归遍历代码

以下是二叉树先序遍历的非递归实现代码：

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

def preorderTraversal(root):
    if not root:
        return []

    stack = []
    result = []
    node = root

    while node or stack:
        while node:
            result.append(node.val)
            stack.append(node)
            node = node.left

        node = stack.pop()
        node = node.right

    return result

这段代码使用了一个栈来模拟递归的过程。首先将根节点入栈，然后进入循环，如果当前节点存在，则将其值加入结果列表，并将当前节点入栈，然后继续遍历其左子树。如果当前节点为空，则从栈中弹出一个节点，并继续遍历其右子树。重复这个过程直到栈为空。最后返回结果列表即为先序遍历的结果。

相关问题

先序非递归遍历算法遍历二叉树 ​中序非递归遍历算法遍历二叉树 ​后序非递归遍历算法遍历二叉树 ​层序遍历二叉树

好的，我可以给您介绍一下二叉树的四种非递归遍历算法以及层序遍历。

先序非递归遍历算法：
1. 新建一个栈，将根节点入栈。
2. 当栈不为空时，取出栈顶元素并访问它。
3. 将当前节点的右子节点（如果存在）入栈，再将左子节点（如果存在）入栈。
4. 重复步骤2-3，直到栈为空。

中序非递归遍历算法：
1. 新建一个栈，将根节点入栈。
2. 如果当前节点不为空，则将当前节点的左子节点全部入栈，并将当前节点置为左子节点。
3. 如果当前节点为空，则取出栈顶元素并访问它，将当前节点置为它的右子节点。
4. 重复步骤2-3，直到栈为空。

后序非递归遍历算法：
1. 新建两个栈：s1和s2，将根节点入s1。
2. 当s1不为空时，取出栈顶元素并将其压入s2中。
3. 将当前节点的左子节点（如果存在）入s1，再将右子节点（如果存在）入s1。
4. 重复步骤2-3，直到s1为空。
5. 依次访问s2中的元素即可得到后序遍历结果。

层序遍历算法：
1. 新建一个队列，将根节点入队。
2. 当队列不为空时，取出队首元素并访问它。
3. 将当前节点的左子节点（如果存在）入队，再将右子节点（如果存在）入队。
4. 重复步骤2-3，直到队列为空。

二叉树的先序非递归遍历

二叉树的先序非递归遍历，也称为前序遍历，是一种从根节点开始，然后遍历左子树，最后遍历右子树的顺序。非递归实现通常使用栈来模拟递归过程。以下是步骤：

1. 创建一个空栈和一个指向当前节点的指针（初始为根节点）。
2. 当栈不为空或当前节点不为空时，执行以下操作：
a. 如果当前节点不为空，将当前节点压入栈中，并将当前节点指向下个节点（即左子节点）。
b. 如果当前节点为空，从栈顶取出下一个节点作为当前节点。
3. 对取出的当前节点进行操作（如打印节点值），然后更新当前节点为它的右子节点。
4. 重复步骤2直到栈为空且当前节点也为空。

非递归先序遍历的伪代码示例：

void preorderNonRecursive(Node* root) {
    Stack<Node*> stack;
    Node* current = root;
    while (stack.empty() || current != nullptr) {
        // 如果当前节点不为空，压入栈并移动到左子节点
        if (current != nullptr) {
            stack.push(current);
            current = current->left;
        } 
        // 如果当前节点为空，从栈中弹出节点并访问
        else {
            current = stack.top();
            stack.pop();
            // 执行当前节点的操作，比如打印节点值
            ProcessNode(current);
            current = current->right;
        }
    }
}