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

【C++刷题】二叉树基础OJ题

news 来源：原创 2025/9/15 1:09:22

📝前言说明：
本专栏主要记录本人的基础算法学习以及刷题记录，使用语言为C++。
每道题我会给出LeetCode上的题号（如果有题号），题目，以及最后通过的代码。没有题号的题目大多来自牛客网。对于题目的讲解，主要是个人见解，如有不正确，欢迎指正，一起进步！

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C++学习笔记，C语言入门基础，python入门基础，python刷题专栏
🎀CSDN主页愚润泽

题目

965. 单值二叉树
104. 二叉数的最大深度
144. 二叉树的前序遍历
100. 相同的树
101. 对称二叉树
572. 另一棵树的子树
牛客网KY11 二叉树遍历

965. 单值二叉树

在这里插入图片描述
大问题化小问题：如果该树是一个单值二叉树，则左右子树也一定是
处理单个问题思路：判断一条边上的两个节点的值想不想同。

class Solution {
public:bool isUnivalTree(TreeNode* root) {if(!root){return true;}if(root->left && (root -> val != root -> left -> val)){return false;}if(root->right && (root->val != root -> right -> val)){return false;}return isUnivalTree(root -> left) && isUnivalTree(root -> right);}
};

104. 二叉数的最大深度

在这里插入图片描述
大问题化小问题：一棵树的最大深度 = max(左子树最大深度，右子树最大深度) + 1
处理单个问题：遇到叶子节点，返回 1

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

注意，下面这种错误写法：

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

return maxDepth(root->left) > maxDepth(root->right) ? maxDepth(root->left) + 1 : maxDepth(root->right) + 1;
在这里，因为没有保存左子树和右子树的高度，所以会重新进入maxDepth(root->left)再次计算。并且这里不是简单的计算两次的关系，而是本层调用两次下一层，下一层又调用两次下一次，2的n次的关系。

144. 二叉树的前序遍历

在这里插入图片描述
思路：把对根节点的处理操作放到什么位置就是什么遍历

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {if(root == nullptr){return ans;}ans.push_back(root->val);preorderTraversal(root -> left);preorderTraversal(root -> right);return ans;}
private:vector<int> ans;
};

100. 相同的树

在这里插入图片描述
大问题化小问题：如果两棵树相同，则他们的子树也一定相同
处理单个问题：1，保证以root为根的树的结构相同，2，保证节点的值相同

class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {if((!p && q) || (p && !q)) {return false;}if(!p && !q) {return true;}return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);}
};

101. 对称二叉树

在这里插入图片描述
思路：因为根节点只有一个，所以不用管根节点，将树拆分成左右子树。对称，即：一颗树的左子树等于另一棵树的右子树

class Solution {bool isSametree(TreeNode* p, TreeNode* q){if(!p || !q) //这个确保树的结构是一样的{return p == q;}return p->val == q->val && isSametree(p->left,q->right) && isSametree(p->right,q->left);}
public:bool isSymmetric(TreeNode* root) {return isSametree(root->left, root->right);}
};

572. 另一棵树的子树

能复用代码的情况下，我劲量复用了
在这里插入图片描述
思路：遍历整棵树，以不同的节点为根节点，判断是否和subRoot相同

画一下递归图：
在这里插入图片描述

class Solution {bool isSametree(TreeNode* p, TreeNode* q){if(!p || !q){return p == q;}return p->val == q->val && isSametree(p->left, q->left) && isSametree(p->right, q->right);}
public:bool isSubtree(TreeNode* root, TreeNode* subRoot) {if(!root){return false;}if(root->val == subRoot->val && isSametree(root, subRoot)){return true;}return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);}
};

牛客网KY11 二叉树遍历

在这里插入图片描述

#include <iostream>
#include<string>
using namespace std;// 注意：私有变量只能在类内被访问，及时外部有类的指针，也不能访问该类的私有变量
struct node 
{node(char c): val(c){}char val;node* left = nullptr;node* right = nullptr;
};// 传引用或者指针...，才能修改外部的变量，不然修改的是实参的拷贝（即临时变量）
void build(node*& root, string& str) 
{char c = str[0];str = str.substr(1); // 把第一个元素删掉if(c == '#'){return;}if(root == nullptr) // 当根节点不存在{root = new node(c);}build(root->left, str);build(root->right, str);
}void mid(node* root)
{if(root == nullptr){return;}mid(root->left);cout << root->val << ' ';mid(root->right);
}int main() {string str;while (cin >> str) { // 注意 while 处理多个 casenode* root = nullptr;build(root, str);mid(root);}
}

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！

题目