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

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

vector<int> inorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> res;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        while (cur) {
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top();
        st.pop();
        res.push_back(cur->val);
        cur = cur->right;
    }
    return res;
}

该代码使用了栈来模拟递归过程，具体实现如下：

1. 初始化栈和结果数组，将当前节点指向根节点。

2. 当前节点不为空或栈不为空时，执行以下操作：

a. 当前节点不为空时，将当前节点入栈，并将当前节点指向其左子节点，直到当前节点为空。

b. 当前节点为空时，从栈中弹出一个节点，将其值加入结果数组中，并将当前节点指向该节点的右子节点。

3. 返回结果数组。

相关问题

非递归中序遍历二叉树代码

非递归中序遍历二叉树通常使用栈数据结构来辅助完成。其基本思路是先将左子树的所有节点压入栈中，然后访问当前节点（根节点），接着访问右子树。以下是使用Python实现的一个示例：

def inorder_traversal(root):
    stack = []
    current = root

    while True:
        # 当前节点为空或者还有未处理的左子节点时
        while current:
            stack.append(current)
            current = current.left

        # 如果栈不为空并且顶部元素为右子节点，则弹出并访问
        if not stack:
            return
        current = stack.pop()
        print(current.value)  # 替换成实际的数据访问操作

        # 将焦点移动到弹出节点的右子树
        current = current.right

在这个代码中，我们不断从左子树将节点压入栈，直到遇到空节点。然后，我们依次取出栈顶的节点并访问，再将焦点切换到右子树，直到栈为空为止。

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

非递归中序遍历二叉树通常使用栈数据结构来实现，这样可以避免直接使用递归调用带来的额外函数调用开销。以下是C++中的非递归中序遍历二叉树的代码示例：

#include <iostream>
#include <stack>

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

void nonRecursiveInOrderTraversal(TreeNode* root) {
    std::stack<TreeNode*> stack;
    TreeNode* current = root;

    while (current != nullptr || !stack.empty()) {
        // 将所有左子节点压入栈中
        while (current != nullptr) {
            stack.push(current);
            current = current->left;
        }

        // 弹出栈顶元素并访问，然后移动到其右子节点
        current = stack.top();
        stack.pop();
        std::cout << current->val << " ";
        
        current = current->right;
    }
}

int main() {
    // 假设有一个已经构建好的二叉树
    // 这里省略实际创建二叉树的代码
    nonRecursiveInOrderTraversal(root);  // 调用函数并传入根节点
    return 0;
}

在这个代码中，我们首先将左子节点推入栈中，直到遇到空节点。然后，每次从栈顶取出一个节点，访问它的值，然后移动到其右子节点，继续这个过程，直到栈为空且当前节点也为NULL。