二叉树 有序 遍历 栈

二叉树的遍历有前序遍历、中序遍历和后序遍历。如果要实现有序遍历，可以使用栈来辅助实现。

具体方法如下：

1. 首先将根节点入栈。

2. 循环执行以下步骤，直到栈为空：

a. 取出栈顶节点，并输出该节点的值；

b. 如果该节点有右子节点，将其入栈；

c. 如果该节点有左子节点，将其入栈。

注意：入栈的顺序要保证左子节点先入栈，这样在出栈时才能保证左子树先遍历。

实现代码如下（以中序遍历为例）：

def inorder_traversal(root):
    if not root:
        return []
    stack, res = [], []
    node = root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        res.append(node.val)
        node = node.right
    return res

其中，`stack` 表示栈，`res` 表示结果数组，`node` 表示当前节点。在循环中，如果 `node` 不为空，则将其左子节点入栈，并将 `node` 更新为左子节点；如果 `node` 为空，则从栈中取出一个节点，并将其值加入到 `res` 中，并将 `node` 更新为该节点的右子节点。

相关问题

二叉树 有序 遍历 非递归

二叉树的非递归遍历需要借助栈来实现，以下是三种不同的非递归遍历方法：

1. 非递归先序遍历：

首先将根节点入栈，然后重复以下步骤直到栈为空：

1. 弹出栈顶节点，输出该节点的值。
2. 如果该节点有右子树，将右子树入栈。
3. 如果该节点有左子树，将左子树入栈。

代码实现：

void preorderTraversal(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        cout << node->val << " ";
        if (node->right) s.push(node->right);
        if (node->left) s.push(node->left);
    }
}

2. 非递归中序遍历：

首先将根节点入栈，然后重复以下步骤直到栈为空：

1. 将左子树入栈，直到没有左子树可入栈。
2. 弹出栈顶节点，输出该节点的值。
3. 将右子树入栈。

代码实现：

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

3. 非递归后序遍历：

首先将根节点入栈，然后重复以下步骤直到栈为空：

1. 将左子树入栈，直到没有左子树可入栈。
2. 检查栈顶节点的右子树是否已经被访问过，如果是则弹出栈顶节点并输出该节点的值，否则将右子树入栈并标记为已访问。

代码实现：

void postorderTraversal(TreeNode* root) {
    if (!root) return;
    stack<pair<TreeNode*, bool>> s;
    s.push(make_pair(root, false));
    while (!s.empty()) {
        pair<TreeNode*, bool> p = s.top();
        s.pop();
        TreeNode* node = p.first;
        bool visited = p.second;
        if (visited) {
            cout << node->val << " ";
        } else {
            s.push(make_pair(node, true));
            if (node->right) s.push(make_pair(node->right, false));
            if (node->left) s.push(make_pair(node->left, false));
        }
    }
}

需要注意的是，在非递归后序遍历中需要额外记录每个节点的右子树是否已经被访问过。

二叉树的遍历方法练习

二叉树的遍历主要有三种基本方法：前序遍历、中序遍历和后序遍历。这些遍历方法是针对每个节点的访问顺序，它们可以帮助我们按照特定的规则访问树的所有节点。

1. **前序遍历**（Preorder Traversal）：首先访问根节点，然后递归地遍历左子树，最后遍历右子树。通常表示为：根-左-右。

2. **中序遍历**（Inorder Traversal）：先遍历左子树，然后访问根节点，最后遍历右子树。对于排序二叉搜索树，中序遍历会得到一个有序序列。表示为：左-根-右。

3. **后序遍历**（Postorder Traversal）：首先遍历左子树，接着遍历右子树，最后访问根节点。这种遍历常用于计算表达式树的值。表示为：左-右-根。

此外，还有一种非递归的遍历方法是使用栈（Stack），如层序遍历（Level Order Traversal）或广度优先搜索（Breadth-First Search），它按层次顺序访问节点。