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

二叉树的中序遍历是按照「左-根-右」的顺序遍历二叉树的节点。非递归实现可以使用栈来模拟递归的过程。具体来说：

1. 创建一个空栈，并将根节点入栈。

2. 只要栈不为空，就执行以下操作：
a. 将当前节点移动到左子树，并将左子树的根节点入栈，重复此操作直到当前节点为空。
b. 当前节点为空时，说明已经遍历完了当前节点的左子树，将栈顶元素出栈，访问该节点，并将当前节点移动到右子树。
c. 重复步骤2a和2b直到栈为空。

代码实现如下：

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

相关问题

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

C语言实现二叉树中序遍历非递归同样需要使用栈来实现，具体步骤如下：

1. 新建一个栈和一个指针变量p，初始时p指向根节点，栈为空。
2. 循环执行以下步骤，直到栈为空且p为空：

a. 如果p不为空，则将p入栈，并将p指向其左子节点。

b. 如果p为空，则将栈顶元素出栈并输出，然后将p指向栈顶元素的右子节点。

下面是该算法的C语言实现代码：

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void inorderTraversal(struct TreeNode* root) {
    struct TreeNode* stack[1000];
    int top = -1;
    struct TreeNode* p = root;
    while (top != -1 || p != NULL) {
        if (p != NULL) {
            stack[++top] = p;
            p = p->left;
        }
        else {
            struct TreeNode* node = stack[top--];
            printf("%d ", node->val);
            p = node->right;
        }
    }
}

其中，struct TreeNode定义了二叉树节点的结构体，val是节点的值，left和right分别是左右子节点的指针。该算法的时间复杂度为O(n)，空间复杂度为O(h)，其中h为二叉树的高度。

二叉树中序遍历非递归

### 回答1：
二叉树的中序遍历非递归实现需要借助栈来实现。具体步骤如下：

1. 首先将根节点入栈；

2. 当栈不为空时，取出栈顶节点，如果该节点有左子树，则将其左子树入栈；

3. 如果该节点没有左子树，则访问该节点，并将其右子树入栈；

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

下面是Java代码实现：

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        if (cur != null) {
            stack.push(cur);
            cur = cur.left;
        } else {
            cur = stack.pop();
            res.add(cur.val);
            cur = cur.right;
        }
    }
    return res;
}

其中，TreeNode是二叉树的节点类，val表示节点值，left和right表示左右子节点。

### 回答2：
二叉树的中序遍历是指按照左子树、根节点、右子树的顺序遍历二叉树。通常，我们使用递归算法来实现二叉树的遍历操作。然而，递归算法利用了系统的函数调用栈，当二叉树的高度非常大时，递归可能会导致栈溢出的问题。因此，我们需要考虑使用非递归的方式来实现二叉树的中序遍历。

以下是一种基于栈的非递归中序遍历的思路：

1. 首先，创建一个栈和一个指针指向二叉树的根节点。
2. 如果指针不为空或者栈不为空，则继续遍历二叉树。
3. 当指针不为空时，将指针指向的节点压入栈中，并将指针指向其左子节点。
4. 当指针为空时，说明左子树已经遍历完毕，此时从栈中弹出一个节点并访问它，并将指针指向其右子节点。
5. 重复步骤3和4，直到指针为空且栈为空。

通过以上步骤，我们可以按照中序遍历的顺序遍历整个二叉树，且不使用递归算法。在每次遍历时，会将当前节点的左子节点全部入栈，然后再访问栈顶节点、访问右子节点。通过栈的结构，能够保持遍历顺序并避免出现栈溢出的问题。

这种非递归的中序遍历实现方式具有较好的效率和空间利用率，适用于各种规模的二叉树的遍历。