非递归遍历二叉树

非递归遍历二叉树通常使用栈来实现，具体步骤如下：

1. 创建一个栈和一个指针，指向二叉树的根节点。
2. 当指针不为空或者栈不为空时，执行以下操作：
1. 如果当前指针不为空，将其压入栈中，并将指针移动到左子树。
2. 如果当前指针为空，则将栈顶节点弹出，访问该节点，并将指针移动到右子树。
3. 遍历完成。

以下是中序遍历的代码示例：

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

其中，`root`为二叉树的根节点，`stack`为栈，`res`为遍历结果，`node`为当前指针。

相关问题

非递归遍历二叉树C语言

非递归遍历二叉树是指在不使用递归的情况下，按照某种顺序遍历二叉树的节点。在C语言中，可以使用栈来实现非递归遍历二叉树。

以下是三种常见的非递归遍历二叉树的方法：

1. 非递归前序遍历：
非递归前序遍历的思路是先访问根节点，然后将右子节点入栈，再将左子节点入栈。具体步骤如下：
1) 创建一个栈，并将根节点入栈。
2) 循环执行以下步骤直到栈为空：
a) 弹出栈顶节点并访问。
b) 如果该节点有右子节点，则将右子节点入栈。
c) 如果该节点有左子节点，则将左子节点入栈。

2. 非递归中序遍历：
非递归中序遍历的思路是先将左子节点入栈，然后访问根节点，最后再处理右子节点。具体步骤如下：
1) 创建一个栈，并将根节点入栈。
2) 循环执行以下步骤直到栈为空：
a) 将当前节点的所有左子节点入栈，直到没有左子节点。
b) 弹出栈顶节点并访问。
c) 处理该节点的右子节点。

3. 非递归后序遍历：
非递归后序遍历的思路是先将根节点入栈，然后按照右子节点、左子节点的顺序入栈。具体步骤如下：
1) 创建两个栈，一个用于存储节点，一个用于存储遍历结果。
2) 将根节点入栈1。
3) 循环执行以下步骤直到栈1为空：
a) 弹出栈1顶部节点并将其入栈2。
b) 如果该节点有左子节点，则将左子节点入栈1。
c) 如果该节点有右子节点，则将右子节点入栈1。
4) 循环执行以下步骤直到栈2为空：
a) 弹出栈2顶部节点访问。

非递归遍历二叉树c++

非递归遍历二叉树是指在不使用递归函数的情况下，对二叉树进行遍历的方法。以下是三种非递归遍历二叉树的方法：

1. 非递归中序遍历二叉树

中序遍历二叉树的顺序是：左子树 -> 根节点 -> 右子树。使用栈来保存未被访问的节点，具体步骤如下：
1）从根节点开始，将当前节点入栈。
2）如果当前节点有左子树，则将左子树入栈并进入左子树，重复步骤2，直到左子树为空。
3）从栈中弹出节点，访问该节点。
4）如果该节点有右子树，则将右子树入栈并进入右子树，重复步骤2、3、4。

2. 非递归先序遍历二叉树

先序遍历二叉树的顺序是：根节点 -> 左子树 -> 右子树。使用栈来保存未被访问的节点，具体步骤如下：
1）从根节点开始，将当前节点入栈。
2）从栈中弹出节点，访问该节点。
3）如果该节点有右子树，则将右子树入栈。
4）如果该节点有左子树，则将左子树入栈。
5）重复步骤2、3、4，直到栈为空。

3. 非递归后序遍历二叉树

后序遍历二叉树的顺序是：左子树 -> 右子树 -> 根节点。使用两个栈来实现，具体步骤如下：
1）将根节点入栈1。
2）从栈1中弹出节点，并将该节点入栈2。
3）如果该节点有左子树，则将左子树入栈1。
4）如果该节点有右子树，则将右子树入栈1。
5）重复步骤2、3、4，直到栈1为空。
6）从栈2中依次弹出节点并访问。