二叉树算法详解和C++代码示例

二叉树（Binary Tree）是数据结构中的基础类型，广泛应用于查找、排序、图结构、表达式计算等算法中。下面将从 概念定义 → 分类 → 常用操作 → 核心算法 → C++代码示例 全面介绍。

一、二叉树基本概念

二叉树是一种每个节点最多有两个子节点（左孩子和右孩子）的树结构。常见术语：

• 根节点（root）：没有父节点的节点
• 叶子节点：没有任何子节点
• 高度：节点到叶子节点最长路径上的边数
• 完全二叉树：除了最后一层，其他层节点都满，且最后一层节点从左向右排列
• 满二叉树：所有非叶节点都有两个子节点

二、常见二叉树类型

三、常见操作和算法

四、遍历方式详解与代码

1. 递归遍历（先序、中序、后序）

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

// 先序
void preorder(TreeNode* root) {
    if (!root) return;
    std::cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

// 中序
void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    std::cout << root->val << " ";
    inorder(root->right);
}

// 后序
void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    std::cout << root->val << " ";
}

2. 层序遍历（BFS）

#include <queue>
void levelOrder(TreeNode* root) {
    if (!root) return;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* cur = q.front(); q.pop();
        std::cout << cur->val << " ";
        if (cur->left) q.push(cur->left);
        if (cur->right) q.push(cur->right);
    }
}

五、常见算法题示例（C++）

1. 判断是否为合法 BST

bool isValidBST(TreeNode* root, TreeNode* min = nullptr, TreeNode* max = nullptr) {
    if (!root) return true;
    if ((min && root->val <= min->val) || (max && root->val >= max->val)) return false;
    return isValidBST(root->left, min, root) && isValidBST(root->right, root, max);
}

2. 二叉树最大深度

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + std::max(maxDepth(root->left), maxDepth(root->right));
}

3. 路径总和是否等于 target

bool hasPathSum(TreeNode* root, int sum) {
    if (!root) return false;
    if (!root->left && !root->right) return sum == root->val;
    return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}

六、二叉搜索树（BST）操作实现

插入节点

TreeNode* insert(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val < root->val) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

查找最小值

int findMin(TreeNode* root) {
    while (root->left) root = root->left;
    return root->val;
}

七、刷题推荐（适合 LeetCode）

八、补充：建树方法

TreeNode* buildTree(const std::vector<int>& nodes, int& i) {
    if (i >= nodes.size() || nodes[i] == -1) { ++i; return nullptr; }
    TreeNode* root = new TreeNode(nodes[i++]);
    root->left = buildTree(nodes, i);
    root->right = buildTree(nodes, i);
    return root;
}
// 示例：{-1表示空指针}
// [1, 2, -1, -1, 3, -1, -1] 构建一颗根为1，左右为2,3的树

总结