二叉树的中序非递归遍历思路

二叉树的中序非递归遍历同样可以使用栈来实现。具体思路如下：

1. 首先，创建一个空栈和一个指向根节点的指针。

2. 进入循环，直到栈为空且当前节点指针为空为止。

3. 在循环中，将当前节点以及其所有左子节点依次入栈，直到当前节点为空。

4. 弹出栈顶节点，并输出该节点的值。

5. 将当前节点指针指向弹出节点的右子节点。

6. 重复步骤3至5，直到循环结束。

这样就可以按照中序遍历的顺序输出二叉树的所有节点值。

相关问题

中序非递归遍历二叉树C++

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

#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

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

int main() {
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);
    inorderTraversal(root); // 输出：1 3 2
    return 0;
}

中序非递归遍历二叉树

以下是中序非递归遍历二叉树的Python实现：

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

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

该算法使用了一个栈来模拟递归过程，具体实现如下：

1. 初始化一个空列表res和一个空栈stack。
2. 当根节点root不为空或者栈stack不为空时，执行以下操作：
1. 当root不为空时，将root入栈，并将root更新为root的左子节点。
2. 当root为空时，从栈中弹出一个节点，并将该节点的值加入到res中，然后将root更新为该节点的右子节点。
3. 当栈为空时，遍历结束，返回res。