蓝桥杯 二叉树

二叉树全面解析（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);
    }
};

​​算法分析​​：

1. ​​DFS深度优先搜索​​：系统地遍历所有可能路径

2. ​​路径和计算​​：维护currentSum变量实时计算路径和

3. ​​终止条件​​：到达叶子节点时验证路径和

4. ​​时间复杂度​​：O(n) 每个节点访问一次

5. ​​空间复杂度​​：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; // 输出应为3
    return 0;
}

六、备赛建议与总结

1. 重点掌握内容

• 递归思想在二叉树中的应用

• 三种基本遍历方式及其变种

• 二叉搜索树的性质与操作

• 路径类问题的解题模式

2. 常见考察方向

1. ​​结构特性问题​​：对称性、平衡性判断

2. ​​遍历变种​​：Z字形遍历、垂序遍历

3. ​​构造问题​​：根据遍历序列重建二叉树

4. ​​路径问题​​：最大路径和、特定路径查找

5. ​​最近公共祖先(LCA)​​问题

3. 解题技巧

• 递归时明确终止条件和递归公式

• 对于路径问题，考虑回溯或维护状态变量

• 层次遍历时记录层级信息

• 二叉搜索树问题利用其中序有序特性

通过系统掌握这些知识和技巧，可以应对大多数二叉树相关算法题目。建议多练习各种变种题目，培养递归思维和树结构分析能力。