求二叉树中序遍历递归

在二叉树的中序遍历中，我们按照“左-根-右”的顺序访问每个节点，即先遍历左子树，然后访问根节点，最后遍历右子树。递归实现这个过程相对简单，主要是通过三个步骤：

1. **基本情况**：如果当前节点为空，那么结束递归返回。
2. **递归处理**：如果当前节点不空，首先对左子树进行递归遍历，然后访问当前节点（`print(root.val)`）。
3. **递归继续**：对右子树进行递归遍历。

以下是使用Python的递归函数示例：

def inorder_traversal(root):
    if root is not None:  # 如果节点不为空
        inorder_traversal(root.left)  # 遍历左子树
        print(root.val)  # 访问当前节点
        inorder_traversal(root.right)  # 遍历右子树

# 使用示例：
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

inorder_traversal(root)  # 输出: 4, 2, 5, 1, 3

相关问题

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

在C语言中，二叉树的中序遍历通常采用递归的方式来实现。中序遍历的顺序是先左子树、然后根节点、最后右子树。以下是递归实现中序遍历的简单代码示例：

// 定义二叉树结点结构体
typedef struct TreeNode {
    int val;      // 节点值
    struct TreeNode* left;  // 左子节点指针
    struct TreeNode* right; // 右子节点指针
} TreeNode;

// 中序遍历函数
void inorderTraversal(TreeNode* root) {
    if (root != NULL) { // 如果当前节点非空
        inorderTraversal(root->left); // 先访问左子树
        printf("%d ", root->val);   // 输出当前节点值
        inorderTraversal(root->right); // 再访问右子树
    }
}

在这个代码中，`inorderTraversal` 函数接收一个二叉树的根节点作为参数，如果节点存在，就对左子树进行递归遍历，然后再访问自身（输出节点值），最后递归遍历右子树。如果节点为空，则停止递归。

二叉树中序遍历非递归

### 回答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，直到指针为空且栈为空。

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

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