树算法专题：遍历、BST 与 C++ 实战

一、树基础概念：二叉/满/完全/平衡/BST

树（Tree）是一种由 n 个有限节点组成的具有层次关系的集合。之所以叫"树"，是因为它看起来像一棵倒挂的树——根朝上，叶朝下。树是图的特例：无环的连通图。

在算法题中，二叉树（Binary Tree）是最常见的结构——每个节点最多有两个子节点，分别称为左子节点和右子节点。下面我们通过图解对比四种重要的二叉树变体。

1.1 TreeNode 的 C++ 定义

LeetCode 中二叉树节点使用标准定义，我们在整篇文章中统一使用：

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

二、前中后序 DFS 遍历原理

深度优先搜索（DFS）沿着一条分支尽可能深地走，走到底再回溯。对二叉树而言，DFS 有三种变体，区别仅在于"访问当前节点"在什么时机执行：

"前/中/后"指的就是根节点被访问的位置：在最前面就是前序，在中间就是中序，在最后面就是后序。下面用同一棵树直观对比三种遍历的访问顺序。

2.1 递归栈展开过程

递归的本质是系统帮你维护了一个调用栈。理解递归遍历的关键，是理解每次函数调用时"入栈、递归、回溯"的全过程。下面以中序遍历为例，可视化递归栈的变化：

三、示例一：LeetCode 144/94/145 三序遍历

题目：分别实现二叉树的前序、中序、后序遍历，返回节点值的数组。要求同时给出递归和迭代（手动栈）两种实现。

3.1 完整 C++ 代码（递归 + 迭代）

#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

// ===== 公共定义 =====
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// ============================================================
// 1. 前序遍历（LeetCode 144）：根 → 左 → 右
// ============================================================

// 递归写法
void preRecur(TreeNode* root, vector<int>& res) {
    if (root == nullptr) return;           // 空节点直接返回
    res.push_back(root->val);               // ① 先访问根
    preRecur(root->left, res);              // ② 再递归左子树
    preRecur(root->right, res);             // ③ 最后递归右子树
}
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    preRecur(root, res);
    return res;
}

// 迭代写法（栈）
vector<int> preorderIter(TreeNode* root) {
    vector<int> res;
    if (root == nullptr) return res;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top(); st.pop();
        res.push_back(node->val);           // 出栈即访问
        // 注意：栈 LIFO，为了"左先于右"出栈，必须先压右再压左
        if (node->right) st.push(node->right);
        if (node->left)  st.push(node->left);
    }
    return res;
}

// ============================================================
// 2. 中序遍历（LeetCode 94）：左 → 根 → 右
// ============================================================

// 递归写法
void inRecur(TreeNode* root, vector<int>& res) {
    if (root == nullptr) return;
    inRecur(root->left, res);               // ① 先递归左
    res.push_back(root->val);               // ② 左空了才访问根
    inRecur(root->right, res);              // ③ 最后递归右
}
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    inRecur(root, res);
    return res;
}

// 迭代写法（指针 + 栈，经典"一路向左"法）
vector<int> inorderIter(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        // 第一步：一路向左，沿路节点全部入栈
        while (cur) {
            st.push(cur);
            cur = cur->left;
        }
        // 第二步：左走到头了，栈顶就是"最左未访问"节点
        cur = st.top(); st.pop();
        res.push_back(cur->val);            // 访问根
        cur = cur->right;                   // 转向右子树，下一轮重复
    }
    return res;
}

// ============================================================
// 3. 后序遍历（LeetCode 145）：左 → 右 → 根
// ============================================================

// 递归写法
void postRecur(TreeNode* root, vector<int>& res) {
    if (root == nullptr) return;
    postRecur(root->left, res);             // ① 左
    postRecur(root->right, res);            // ② 右
    res.push_back(root->val);               // ③ 根（最后）
}
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    postRecur(root, res);
    return res;
}

// 迭代写法：技巧法——"根右左"入栈，然后 reverse 得到"左右根"
vector<int> postorderIter(TreeNode* root) {
    vector<int> res;
    if (root == nullptr) return res;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top(); st.pop();
        res.push_back(node->val);           // 按"根→右→左"顺序收集
        if (node->left)  st.push(node->left);   // 先压左，后出
        if (node->right) st.push(node->right);  // 后压右，先出
    }
    reverse(res.begin(), res.end());       // 反转 = 左→右→根
    return res;
}

四、层序 BFS 遍历原理

广度优先搜索（BFS）又叫"层序遍历"，它从上到下、从左到右，一层一层地访问节点。BFS 的核心数据结构是队列（Queue）——FIFO 的特性正好保证"先入队的层先被处理"。

4.1 BFS 与 DFS 对比

五、示例二：LeetCode 102 层序遍历

题目（LeetCode 102）：给定二叉树根节点 root，返回其节点值的层序遍历结果（即按层分组，从上到下、每层从左到右）。

5.1 过程图

5.2 C++ 完整代码

#include <vector>
#include <queue>
using namespace std;

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

// LeetCode 102：二叉树的层序遍历
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;     // 结果二维数组：每层一个 vector
    if (root == nullptr) return res;

    queue<TreeNode*> q;             // BFS 的核心：队列
    q.push(root);

    while (!q.empty()) {
        int size = q.size();         // 关键：固定本层节点数！
        vector<int> level;          // 本层的收集数组

        // 只处理本层的 size 个节点，多一个都不弹
        for (int i = 0; i < size; ++i) {
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);

            // 孩子入队，作为下一层的预备
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(level);         // 本层完成，加入结果
    }
    return res;
}

六、BST 二叉搜索树原理

二叉搜索树（Binary Search Tree, BST）是一种"自带有序性"的二叉树。它的核心性质只有一条，但衍生出强大的查找、插入、删除能力：

6.1 BST 插入过程

插入思路：从根开始比较，小于当前节点就往左走，大于就往右走，走到空位置就把新节点挂上去。

6.2 BST 查找与验证

七、示例三：LeetCode 98 验证 BST

题目（LeetCode 98）：给定一个二叉树，判断其是否是一个有效的二叉搜索树。

7.1 思路一：中序有序性证明

最优雅的解法。由 BST 定义可直接推出以下等价关系：

因此只需中序遍历并记录前一个值，若出现 cur.val ≤ prev 就返回 false。

7.2 完整 C++ 代码

#include <stack>
#include <climits>
using namespace std;

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

// 方法 1：中序遍历 + 记录前驱（迭代写法，避免递归爆栈）
bool isValidBST(TreeNode* root) {
    if (root == nullptr) return true;

    stack<TreeNode*> st;
    TreeNode* cur = root;
    long long prev = (long long)INT_MIN - 1;  // 用 long long 防 INT_MIN 越界

    while (cur || !st.empty()) {
        // 一路向左入栈（标准中序迭代模板）
        while (cur) {
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top(); st.pop();

        // ★ 关键检查：当前值必须严格大于前一个
        if ((long long)cur->val <= prev) {
            return false;
        }
        prev = cur->val;  // 更新前驱

        cur = cur->right; // 转向右子树
    }
    return true;
}

// 方法 2：递归 + 上下界（另一种经典思路，供对比）
// 每个节点必须满足 (lowerBound, upperBound) 开区间
bool check(TreeNode* node, long long lower, long long upper) {
    if (node == nullptr) return true;
    // 当前节点的值必须严格落在 (lower, upper) 之内
    if (node->val <= lower || node->val >= upper) return false;
    // 递归左：上界变成当前值；递归右：下界变成当前值
    return check(node->left, lower, node->val)
        && check(node->right, node->val, upper);
}
bool isValidBST2(TreeNode* root) {
    return check(root, (long long)INT_MIN - 1, (long long)INT_MAX + 1);
}

八、示例四：LeetCode 701 BST 插入

题目（LeetCode 701）：给定 BST 根节点和要插入的值 val，将值插入 BST 并返回新的根。保证新值和原 BST 任一节点值都不同。

8.1 插入过程可视化

8.2 C++ 完整代码

#include <queue>
using namespace std;

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

// LeetCode 701：二叉搜索树中的插入操作（递归）
TreeNode* insertIntoBST(TreeNode* root, int val) {
    // ★ 递归终止：走到空位置，创建新节点并返回给父节点
    if (root == nullptr) {
        return new TreeNode(val);
    }

    // val 比当前小 → 应该插入到左子树，于是递归后让 root.left 接住结果
    if (val < root->val) {
        root->left = insertIntoBST(root->left, val);
    }
    // val 比当前大 → 应该插入到右子树，同理让 root.right 接住
    else if (val > root->val) {
        root->right = insertIntoBST(root->right, val);
    }

    // 注意：题目保证 val 不在树中，所以不会遇到 == 的情况
    return root;  // 当前根向上返回，给上一层"接"好
}

// 另一种写法：迭代（用 parent 指针跟踪父节点）
TreeNode* insertIntoBSTIter(TreeNode* root, int val) {
    if (root == nullptr) return new TreeNode(val);

    TreeNode* cur = root;
    TreeNode* parent = nullptr;  // 记录 cur 的父节点

    // 找到插入点：cur 变成 nullptr 时，parent 就是"要挂新节点的父亲"
    while (cur != nullptr) {
        parent = cur;
        if (val < cur->val) cur = cur->left;
        else                 cur = cur->right;
    }

    // 判断挂在左还是右
    if (val < parent->val) parent->left  = new TreeNode(val);
    else                   parent->right = new TreeNode(val);

    return root;
}

九、总结

树是算法面试的高频专题，核心就两条主线：遍历（DFS/BFS）与BST 性质。下面用一张表把本文所有知识收束起来。

进一步刷题建议

• 基础遍历：LeetCode 94/144/145（三序，递归+迭代都要写）
• BFS 层序：LeetCode 102/103/107/199/637
• 深度/平衡：LeetCode 104/110/111/543 直径
• BST 系列：LeetCode 98/700/701/450 删除/230 第 k 小
• 路径/回溯：LeetCode 112 路径和/257 二叉树所有路径
• 构造类：LeetCode 105 前+中序构造/106 中+后序

树是最能体现"递归思想"的数据结构，把这篇文章的所有代码和 SVG 图在脑子里过一遍，再刷完上面的推荐题——你会发现，90% 的树题都逃不出这几个模板的范围。