二叉树的非递归中序遍历，使用栈帧模拟

您好，可以使用栈进行模拟。具体步骤如下：

1. 从根节点开始，将其压入栈中。

2. 将当前节点的左子树全部压入栈中，直到遇到叶子节点。

3. 弹出栈顶节点，输出节点值。

4. 将当前指针指向弹出节点的右子树，回到步骤 2。

5. 重复步骤 3 和 4，直到栈为空。

以下是 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 = []
    cur = root
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        res.append(cur.val)
        cur = cur.right
    return res

希望这个回答能够帮到您。

相关问题

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

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

1. 创建一个空栈和一个指向根节点的指针。
2. 将当前节点指针指向根节点。
3. 循环执行以下步骤，直到栈为空且当前节点指针为空：
- 将当前节点指针的所有左子节点依次入栈，直到当前节点指针为空。
- 弹出栈顶元素作为当前节点，并输出当前节点的值。
- 将当前节点指针指向当前节点的右子节点。

下面是一个示例的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* curr = root;

    while (curr != NULL || !s.empty()) {
        while (curr != NULL) {
            s.push(curr);
            curr = curr->left;
        }

        curr = s.top();
        s.pop();
        cout << curr->val << " ";

        curr = curr->right;
    }
}

int main() {
    // 构造二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    // 非递归中序遍历
    cout << "非递归中序遍历结果：";
    inorderTraversal(root);

    return 0;
}

二叉树非递归中序遍历C语言实现

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

// 定义二叉树结构体
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 定义栈结构体
typedef struct Stack {
    TreeNode** arr;
    int top;
    int maxSize;
} Stack;

// 创建栈
Stack* createStack(int size) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->arr = (TreeNode**)malloc(sizeof(TreeNode*) * size);
    stack->top = -1;
    stack->maxSize = size;
    return stack;
}

// 入栈
void push(Stack* stack, TreeNode* node) {
    if (stack->top == stack->maxSize - 1) {
        return;
    }
    stack->arr[++stack->top] = node;
}

// 出栈
TreeNode* pop(Stack* stack) {
    if (stack->top == -1) {
        return NULL;
    }
    return stack->arr[stack->top--];
}

// 判断栈是否为空
int isEmpty(Stack* stack) {
    return stack->top == -1;
}

// 中序遍历
int* inorderTraversal(TreeNode* root, int* returnSize) {
    *returnSize = 0;
    int* res = (int*)malloc(sizeof(int));
    Stack* stack = createStack(100); // 创建栈
    TreeNode* cur = root;
    while (cur != NULL || !isEmpty(stack)) {
        while (cur != NULL) { // 遍历左子树并入栈
            push(stack, cur);
            cur = cur->left;
        }
        cur = pop(stack); // 左子树遍历完毕，出栈一个节点
        res = (int*)realloc(res, sizeof(int) * (*returnSize + 1));
        res[(*returnSize)++] = cur->val; // 将出栈节点的值加入结果数组
        cur = cur->right; // 遍历右子树
    }
    return res;
}

该实现利用栈来模拟递归的过程，将待遍历的节点入栈，遍历完左子树后出栈一个节点，将其值加入结果数组，然后遍历其右子树。重复以上步骤直到栈为空。