二叉树遍历

// 二叉树节点定义
struct TreeNode {
    int val;            // 节点的值
    TreeNode *left;     // 左子节点指针
    TreeNode *right;    // 右子节点指针

    // 构造函数：方便创建节点
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void preorder(TreeNode* root) {
    if (!root) return;              // 终止条件：空节点，直接返回

    cout << root->val << " ";     // ① 访问根节点（先处理根）
    preorder(root->left);          // ② 递归遍历左子树
    preorder(root->right);         // ③ 递归遍历右子树
}

// 执行过程（以根=1为例）：
// preorder(1) → 打印1
//   preorder(2) → 打印2
//     preorder(4) → 打印4
//     preorder(5) → 打印5
//   preorder(3) → 打印3
// 输出：1 2 4 5 3

void inorder(TreeNode* root) {
    if (!root) return;              // 终止条件

    inorder(root->left);           // ① 先遍历左子树
    cout << root->val << " ";     // ② 再访问根节点
    inorder(root->right);          // ③ 最后遍历右子树
}

// ⭐ 重要性质：BST的中序遍历结果是有序的！
// 如果是二叉搜索树（左子树值 < 根值 < 右子树值），
// 中序遍历出来的序列一定是升序的。

void postorder(TreeNode* root) {
    if (!root) return;              // 终止条件

    postorder(root->left);         // ① 先遍历左子树
    postorder(root->right);        // ② 再遍历右子树
    cout << root->val << " ";     // ③ 最后访问根节点
}

// 后序遍历的应用：释放二叉树内存
// 必须先释放子节点，再释放根节点（后序天然满足这个顺序）

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

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

unordered_map<int,int> inMap;  // 中序值→下标的映射，方便快速查找

TreeNode* build(vector<int>& pre, int preL, int preR,
                vector<int>& in, int inL, int inR) {
    if (preL > preR) return nullptr;   // 空区间

    int rootVal = pre[preL];           // 前序第一个就是根
    TreeNode* root = new TreeNode(rootVal);

    int inRoot = inMap[rootVal];       // 在中序中找到根的位置
    int leftSize = inRoot - inL;       // 左子树的大小

    // 递归构建左子树和右子树
    root->left = build(pre, preL+1, preL+leftSize, in, inL, inRoot-1);
    root->right = build(pre, preL+leftSize+1, preR, in, inRoot+1, inR);

    return root;
}

// 调用：
// for (int i = 0; i < n; i++) inMap[in[i]] = i;
// TreeNode* root = build(pre, 0, n-1, in, 0, n-1);