引入

我们从小学二年级开始，就学过二叉树了（bushi）

那么，如何用编程实现二叉树的遍历呢？

（这里使用c艹）


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

二叉树的每个结点都是如此定义的

遍历方法

分为前序，中序，后序三种遍历方法。

前序是从根结点开始，访问到最左侧第一个叶子结点后，访问右侧叶子，然后返回上一级（不访问），访问同级右侧结点，然后往下按照先左后右的顺序访问，等左子树访问完毕后，访问右子树。

中序是从左侧第一个叶子结点开始，返回上一级（访问），下一级右侧，返回上上级，右侧最下方左侧结点，然后返回上一级（访问），以此类推。

后序是按从左到右的顺序，左侧第一个叶子结点开始，访问完上一级结点左侧后，去右侧，然后返回上一级。

每种遍历方法又分为递归和非递归两种

非递归方法

1. 前序遍历（非递归）

前序遍历的顺序是：根节点 -> 左子树 -> 右子树。

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result; // 存储遍历结果
    if (!root) return result;

    stack<TreeNode*> stk; // 辅助栈
    stk.push(root);       // 首先将根节点入栈

    while (!stk.empty()) {
        TreeNode* node = stk.top();  // 获取栈顶元素
        stk.pop();                   // 弹出栈顶元素
        result.push_back(node->val); // 访问节点（加入结果）

        // 先压右子节点，再压左子节点，保证左子节点先处理
        if (node->right) stk.push(node->right);
        if (node->left) stk.push(node->left);
    }

    return result;
}

2. 中序遍历（非递归）

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

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

    while (current != NULL || !stack.empty()) {
        // 遍历到最左节点
        while (current != NULL) {
            stack.push(current);
            current = current->left;
        }
        // 处理节点
        current = stack.top();
        stack.pop();
        std::cout << current->val << " ";
        // 转向右子树
        current = current->right;
    }
}

初始化：创建一个栈来存储节点，并将当前节点指向根节点。

遍历左子树：使用一个 while 循环，持续将当前节点的左子节点压入栈中，直到当前节点为 NULL。这一步实际上是在找到最左侧的节点。

处理节点：当当前节点为 NULL 且栈不为空时，弹出栈顶节点，输出该节点的值。这就是中序遍历的核心步骤。

转向右子树：将当前节点更新为弹出的节点的右子节点，继续上述过程。

结束条件：当当前节点为 NULL 且栈为空时，遍历结束。

3. 后序遍历（非递归）

后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

后序遍历的非递归实现较复杂，可以使用两个栈来实现。

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    if (!root) return result;

    stack<TreeNode*> stk1, stk2;
    stk1.push(root);

    // 使用两个栈，stk1用于遍历，stk2用于存储结果
    while (!stk1.empty()) {
        TreeNode* node = stk1.top();
        stk1.pop();
        stk2.push(node);

        // 左子节点和右子节点按顺序压入stk1
        if (node->left) stk1.push(node->left);
        if (node->right) stk1.push(node->right);
    }

    // 将stk2中的节点依次弹出到结果中
    while (!stk2.empty()) {
        result.push_back(stk2.top()->val);
        stk2.pop();
    }

    return result;
}

这三种非递归遍历方法使用栈来模拟递归调用的过程，顺序不同是由于每种遍历访问节点的顺序不同。

递归方法

递归算法是一种非常常见且简单的二叉树遍历实现方式，它依赖函数调用栈的隐式机制来完成节点的访问。在二叉树的递归遍历中，递归函数会按照特定的顺序调用自身来遍历树的各个节点。

1. 前序遍历（递归）

定义

前序遍历的顺序是：先访问根节点，再访问左子树，最后访问右子树。

前序遍历顺序：

根节点 -> 左子树 -> 右子树。

递归算法步骤

先访问当前节点（根节点）。
递归访问左子树。
递归访问右子树。

代码实现

void preorderTraversal(TreeNode* root, vector<int>& result) {
    if (!root) return;                  // 递归终止条件：节点为空

    result.push_back(root->val);         // 访问根节点
    preorderTraversal(root->left, result); // 递归遍历左子树
    preorderTraversal(root->right, result); // 递归遍历右子树
}

过程说明

假设二叉树结构如下：

首先访问根节点 1，然后递归访问它的右子节点 2。
访问 2 后，递归访问 2 的左子节点 3。
访问 3 后，没有更多节点，递归结束。

最终前序遍历的结果为 [1, 2, 3]。

2. 中序遍历（递归）

定义

中序遍历的顺序是：先访问左子树，然后访问根节点，最后访问右子树。

中序遍历顺序：

左子树 -> 根节点 -> 右子树。

递归算法步骤

递归访问左子树。
访问当前节点（根节点）。
递归访问右子树。

代码实现

void inorderTraversal(TreeNode* root, vector<int>& result) {
    if (!root) return;                    // 递归终止条件：节点为空

    inorderTraversal(root->left, result);   // 递归遍历左子树
    result.push_back(root->val);            // 访问根节点
    inorderTraversal(root->right, result);  // 递归遍历右子树
}

过程说明

假设二叉树结构如下：

首先递归访问 1 的左子树，但为空，直接访问根节点 1。
然后递归访问右子树，从 2 开始，递归访问 2 的左子节点 3。
访问完 3，回到 2，访问 2。

最终中序遍历的结果为 [1, 3, 2]。

3. 后序遍历（递归）

定义

后序遍历的顺序是：先访问左子树，再访问右子树，最后访问根节点。

后序遍历顺序：

左子树 -> 右子树 -> 根节点。

递归算法步骤

递归访问左子树。
递归访问右子树。
访问当前节点（根节点）。

代码实现

void postorderTraversal(TreeNode* root, vector<int>& result) {
    if (!root) return;                    // 递归终止条件：节点为空

    postorderTraversal(root->left, result);  // 递归遍历左子树
    postorderTraversal(root->right, result); // 递归遍历右子树
    result.push_back(root->val);             // 访问根节点
}

过程说明

假设二叉树结构如下：

首先递归访问 1 的左子树，空节点返回。
然后递归访问 1 的右子节点 2，继续递归访问 2 的左子节点 3。
访问 3 后返回，访问 2 后返回，最后访问根节点 1。

最终后序遍历的结果为 [3, 2, 1]。

递归遍历的工作原理

递归遍历的核心思想是利用系统调用栈隐式地保存当前节点的状态，并通过函数的自我调用完成对二叉树各个节点的遍历。在每一次递归调用时，栈帧会记录当前函数的上下文（包括参数和本地变量），当递归返回时，栈帧会恢复之前的状态。因此，递归算法中不需要显式地使用栈结构来保存节点状态，递归的函数调用本身就是栈的模拟。

通过遍历确定二叉树

首先，一种遍历是肯定不能的

前序遍历＋后序也不能

但中序＋任意就可以

下面是后序和中序的一个例子

给定二叉树的后序遍历和中序遍历，可以确定这棵二叉树的结构。

后序遍历：dabec
中序遍历：debac

重建二叉树的步骤

后序遍历的特点：后序遍历的最后一个节点是根节点。因此，通过后序遍历可以找到二叉树的根节点。
- 在后序遍历 dabec 中，最后一个元素 c 是二叉树的根节点。
在中序遍历中找到根节点：通过中序遍历，可以将二叉树分为左子树和右子树。
- 中序遍历是 debac，根节点 c 在中序遍历中的位置是最后一位，因此 deba 是左子树，右子树为空。
递归构建左子树：
- 左子树的中序遍历是 deba，左子树的后序遍历是 dabe（从后序遍历中取去掉根节点的部分）。
- 继续对 dabe 和 deba 递归构建。
对左子树进行递归构建：
- 在后序遍历 dabe 中，最后一个元素 e 是左子树的根节点。
- 在中序遍历 deba 中，根节点 e 的位置将 d 和 ba 分为左右子树，左子树为 d，右子树为 ba。
递归构建左子树和右子树：
- 对左子树 d，中序遍历和后序遍历均为 d，因此它是叶子节点。
- 对右子树 ba：
  - 在后序遍历 ba 中，根节点是 a，剩下的 b 是它的左子树。
  - 对左子树 b，中序遍历和后序遍历均为 b，因此它是叶子节点。

最终二叉树的结构

将上述步骤的结果组合在一起，二叉树的形状如下：

    c
   /
  e
 / \
d   a
   /
  b

详细解释

根节点是 c，它的左子树是 e。
节点 e 的左子树是 d，右子树是 a。
节点 a 有一个左子树 b，而 b 和 d 都是叶子节点。

通过后序遍历和中序遍历，我们成功地重建了这棵二叉树。

递归 vs. 非递归

递归遍历：
- 简洁且符合思维逻辑。
- 利用系统调用栈来管理递归状态，不需要手动维护栈。
- 如果树的深度较深，递归深度过大会导致栈溢出。
非递归遍历：
- 使用显式栈来模拟递归，避免了函数调用的开销。
- 更加适合处理非常深的树，避免了递归栈溢出的问题。
- 实现较为复杂，尤其是后序遍历，需要用到两个栈。