当前位置：首页 > news >正文

蓝桥杯二叉树

news 2025/8/16 12:03:40

二叉树全面解析（C++实现）

一、二叉树基本概念

1. 定义与特性

二叉树是每个节点最多有两个子节点的树结构，具有以下性质：

每个节点至多有两棵子树（左子树和右子树）
子树有严格的左右之分（有序树）
第i层最多有2^(i-1)个节点
深度为k的树最多有2^k - 1个节点

2. 特殊二叉树类型

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

满二叉树：所有层的节点数都达到最大值

完全二叉树：除最后一层外均为满的，最后一层节点左对齐

二叉搜索树(BST)：左子树所有节点值 < 根节点值 < 右子树所有节点值

二、二叉树存储结构

1. 链式存储（最常用）

// 创建二叉树示例
TreeNode* createBinaryTree() {//       1//      / \//     2   3//    / //   4  TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);return root;
}

优点：直观反映树的结构，方便动态增删节点

缺点：需要额外空间存储指针

2. 顺序存储（数组表示）

vector<int> tree = {1, 2, 3, 4, INT_MIN, INT_MIN, INT_MIN}; // INT_MIN表示空节点

索引规则：

下标i的节点：左子节点在2i+1，右子节点在2i+2
父节点在⌊(i-1)/2⌋位置

适用场景：完全二叉树的紧凑存储

三、二叉树遍历详解

1. 前序遍历（根→左→右）

void preorder(TreeNode* root, vector<int>& res) {if (!root) return;res.push_back(root->val);  // 先访问根节点preorder(root->left, res); // 再遍历左子树preorder(root->right, res);// 最后遍历右子树
}

应用场景：复制二叉树、前缀表达式

2. 中序遍历（左→根→右）

void inorder(TreeNode* root, vector<int>& res) {if (!root) return;inorder(root->left, res);  // 先遍历左子树res.push_back(root->val);  // 再访问根节点inorder(root->right, res); // 最后遍历右子树
}

重要特性：二叉搜索树的中序遍历结果是升序序列

3. 后序遍历（左→右→根）

void postorder(TreeNode* root, vector<int>& res) {if (!root) return;postorder(root->left, res);  // 先遍历左子树postorder(root->right, res); // 再遍历右子树res.push_back(root->val);    // 最后访问根节点
}

应用场景：删除二叉树、后缀表达式计算

4. 层次遍历（BFS）

vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;if (!root) return result;queue<TreeNode*> q;q.push(root);while (!q.empty()) {int levelSize = q.size();vector<int> currentLevel;for (int i = 0; i < levelSize; ++i) {TreeNode* node = q.front();q.pop();currentLevel.push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}result.push_back(currentLevel);}return result;
}

特点：按层输出节点，可以清晰看到树的结构

四、核心算法实现

1. 计算二叉树深度

int maxDepth(TreeNode* root) {if (!root) return 0;int leftDepth = maxDepth(root->left);   // 计算左子树深度int rightDepth = maxDepth(root->right); // 计算右子树深度return max(leftDepth, rightDepth) + 1;  // 取最大值+1
}

算法思路：递归计算左右子树深度，取较大值加1

2. 查找节点

bool findNode(TreeNode* root, int target) {if (!root) return false;if (root->val == target) return true;  // 当前节点匹配// 递归查找左右子树return findNode(root->left, target) || findNode(root->right, target);
}

3. 镜像翻转二叉树

TreeNode* invertTree(TreeNode* root) {if (root) {// 交换左右子树swap(root->left, root->right);// 递归翻转子树invertTree(root->left);invertTree(root->right);}return root;
}

应用场景：对称性检查、图像处理

4. 验证二叉搜索树

bool isValidBST(TreeNode* root, long min_val = LONG_MIN, long max_val = LONG_MAX) {if (!root) return true;// 检查当前节点值是否在合理范围内if (root->val <= min_val || root->val >= max_val) return false;// 递归检查左右子树，更新范围限制return isValidBST(root->left, min_val, root->val) && isValidBST(root->right, root->val, max_val);
}

关键点：维护值范围约束，确保BST性质

五、蓝桥杯真题实战

题目：二叉树路径和（2020省赛）

问题描述：计算所有从根到叶子的路径中，路径节点值之和等于目标值的路径数量。

class Solution {
public:int pathSum(TreeNode* root, int targetSum) {if (!root) return 0;int count = 0;dfs(root, 0, targetSum, count);return count;}private:void dfs(TreeNode* node, int currentSum, int target, int& count) {if (!node) return;currentSum += node->val; // 更新当前路径和// 到达叶子节点且满足条件if (!node->left && !node->right && currentSum == target) {count++;}// 递归搜索左右子树dfs(node->left, currentSum, target, count);dfs(node->right, currentSum, target, count);}
};

算法分析：

DFS深度优先搜索：系统地遍历所有可能路径
路径和计算：维护currentSum变量实时计算路径和
终止条件：到达叶子节点时验证路径和
时间复杂度：O(n) 每个节点访问一次
空间复杂度：O(h) 递归栈深度，h为树高

测试用例：

int main() {// 构建测试树TreeNode* root = new TreeNode(5);root->left = new TreeNode(4);root->right = new TreeNode(8);root->left->left = new TreeNode(11);root->right->left = new TreeNode(13);root->right->right = new TreeNode(4);root->left->left->left = new TreeNode(7);root->left->left->right = new TreeNode(2);root->right->right->left = new TreeNode(5);root->right->right->right = new TreeNode(1);Solution sol;cout << "路径数量: " << sol.pathSum(root, 22) << endl; // 输出应为3return 0;
}