LeetCode hot 力扣热题100 二叉树的中序遍历(非递归)

以下是代码中每行的详细注释以及整体思路：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        // 定义存储结果的向量，用于存储中序遍历结果
        vector<int> result;

        // 定义一个栈，存储节点和访问状态。pair的第一个元素是节点指针，第二个元素是状态值。
        stack<pair<TreeNode*, int>> stk;

        // 将根节点和初始状态（0）压入栈中
        stk.push(make_pair(root, 0));
        
        // 循环处理栈，直到栈为空
        while (!stk.empty()) {
            // 取出栈顶元素，`node` 是当前节点指针，`type` 是访问状态
            auto [node, type] = stk.top();
            stk.pop(); // 弹出栈顶元素

            // 如果当前节点为空，跳过本次循环
            if (node == nullptr) continue;

            if (type == 0) {
                // 当前节点是第一次访问（状态为 0）
                // 按照右 -> 当前 -> 左的顺序依次入栈
                stk.push(make_pair(node->right, 0)); // 将右子节点入栈，状态为 0
                stk.push(make_pair(node, 1));       // 将当前节点入栈，状态为 1
                stk.push(make_pair(node->left, 0)); // 将左子节点入栈，状态为 0
            } else {
                // 当前节点是第二次访问（状态为 1）
                // 将节点值加入结果向量中
                result.emplace_back(node->val);
            }
        }

        // 返回最终的中序遍历结果
        return result;
    }
};

整体思路

这是一个基于显式栈的非递归中序遍历实现。主要思想是用栈模拟递归的调用栈，借助状态标记（type）实现对节点的多次访问，完成中序遍历（左 -> 根 -> 右）。

1. 状态定义：

• 每个节点会被压栈两次：第一次访问时，状态是 0，此时只是标记，随后按顺序处理右子节点、根节点、左子节点。

• 第二次访问时，状态是 1，表示该节点需要被处理（即将其值存入结果）。

2. 栈操作逻辑：

• 右子树：在遍历根节点前，先将右子树压栈，确保它最后被处理。

• 当前节点：将状态改为 1 后重新压栈，保证处理完左子树后再访问它。

• 左子树：优先压入，保证它最先被处理。

3. 循环条件：

• 栈为空时表示所有节点都已经处理完毕，终止遍历。

运行步骤

假设输入树如下：

       1

        \

         2

        /

       3

• 初始化：

• stk = [(1, 0)]（根节点和初始状态）。

• 第一次循环：

• 弹出 (1, 0)。

• 按右 -> 根 -> 左顺序将节点压栈：

• stk = [(2, 0), (1, 1), (nullptr, 0)]。

• 第二次循环：

• 弹出 (nullptr, 0)，跳过。

• 第三次循环：

• 弹出 (1, 1)。

• result = [1]。

• stk = [(2, 0)]。

• 第四次循环：

• 弹出 (2, 0)。

• 按右 -> 根 -> 左顺序压栈：

• stk = [(nullptr, 0), (2, 1), (3, 0)]。

• 第五次循环：

• 弹出 (3, 0)。

• 按右 -> 根 -> 左顺序压栈：

• stk = [(nullptr, 0), (2, 1), (nullptr, 0), (3, 1), (nullptr, 0)]。

• 第六次循环：

• 弹出 (nullptr, 0)，跳过。

• 第七次循环：

• 弹出 (3, 1)。

• result = [1, 3]。

• stk = [(nullptr, 0), (2, 1)]。

• 第八次循环：

• 弹出 (2, 1)。

• result = [1, 3, 2]。

• stk = []。

• 结束：

• 栈为空，返回结果 [1, 3, 2]。

原文地址：https://blog.csdn.net/qq_51956059/article/details/145242396

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！