二叉树无序遍历的非递归算法

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

1. 首先将根节点入栈。
2. 取出栈顶节点，如果该节点有右子树，则将右子树入栈；如果有左子树，则将左子树入栈。
3. 重复步骤2，直到栈为空。

下面是详细的代码实现：

void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    while (root || !s.empty()) {
        while (root) {
            s.push(root);
            root = root->left;
        }
        root = s.top();
        s.pop();
        cout << root->val << " ";
        root = root->right;
    }
}

其中，TreeNode 是二叉树节点的结构体，包含了 val、left、right 三个成员变量。这段代码实现了二叉树的无序遍历，输出结果即为遍历结果。

相关问题

编写二叉树无序遍历的非递归算法。

二叉树的无序遍历（或称为中序遍历）的非递归算法可以使用栈来实现。具体步骤如下：

1. 从根节点开始，将根节点入栈。
2. 当栈不为空时，取出栈顶节点并将其左子树的所有节点依次入栈，直到左子树为空。
3. 输出栈顶节点的值。
4. 将栈顶节点的右子树入栈。
5. 重复步骤 2-4，直到栈为空。

下面是使用 Python 语言实现的代码示例：

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

def inorder_traversal(root: TreeNode) -> List[int]:
    if not root:
        return []
    res = []
    stack = []
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        node = stack.pop()
        res.append(node.val)
        root = node.right
    return res

在上面的代码中，我们使用了一个栈来存储节点。首先将根节点入栈，然后进入一个循环，不停地取出栈顶节点并进行操作，直到栈为空。在循环中，我们首先将左子树的所有节点入栈，然后输出栈顶节点的值，再将右子树入栈。这样就实现了二叉树的无序遍历的非递归算法。

尝试编写二叉树无序遍历的非递归算法。

二叉树的无序遍历即为先序遍历、中序遍历、后序遍历的任意一种。

以下为二叉树中序遍历的非递归算法实现：

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

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

该算法的主要思路为：

1. 如果当前节点不为空，则将其压入栈中，并将当前节点指向其左子节点，直到当前节点为空。
2. 如果当前节点为空且栈不为空，则弹出栈顶元素，将其值添加到结果列表中，并将当前节点指向其右子节点。
3. 重复步骤1和2，直到当前节点为空且栈为空。

可以根据该思路，进行先序遍历和后序遍历的非递归算法实现。