当前位置：网站首页>刷题笔记-树（Easy）-更新中
刷题笔记-树（Easy）-更新中
2022-06-27 17:57:00 【老闫在努力】
1.遍历相关-DFS
比较简单，不多赘述，特殊的会进行一些笔记
144. 二叉树的前序遍历 - 力扣（LeetCode）
class Solution {
public:
vector<int>ans;
void DFS(TreeNode* root){
if(root==nullptr)return;
ans.emplace_back(root->val);
DFS(root->left);
DFS(root->right);
}
vector<int> preorderTraversal(TreeNode* root) {
DFS(root);
return ans;
}
};94. 二叉树的中序遍历 - 力扣（LeetCode）
class Solution {
public:
vector<int>ans;
vector<int> inorderTraversal(TreeNode* root) {
if(root==nullptr){
return {};
}
if(root->left){
inorderTraversal(root->left);
}
ans.push_back(root->val);
if(root->right){
inorderTraversal(root->right);
}
return ans;
}
};145. 二叉树的后序遍历 - 力扣（LeetCode）
class Solution {
public:
vector<int>ans;
void DFS(TreeNode* root){
if(root==nullptr)return;
DFS(root->left);
DFS(root->right);
ans.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
DFS(root);
return ans;
}
};589. N 叉树的前序遍历 - 力扣（LeetCode）
class Solution {
public:
vector<int>v;
void DFS(Node* root){
if(root==nullptr)return;
v.push_back(root->val);
for(auto x:root->children){
DFS(x);
}
}
vector<int> preorder(Node* root) {
DFS(root);
return v;
}
};590. N 叉树的后序遍历 - 力扣（LeetCode）
这题有个小细节值得注意的，之前我习惯声明一个全局的vector来保存结果，这里的方法将vector作为参数传入函数中，并赋为引用，以实时修改vector的内容。
class Solution {
public:
void helper(const Node* root, vector<int> & res) {
if (root == nullptr) {
return;
}
for (auto & ch : root->children) {
helper(ch, res);
}
res.emplace_back(root->val);
}
vector<int> postorder(Node* root) {
vector<int> res;
helper(root, res);
return res;
}
};2.遍历相关-BFS
637. 二叉树的层平均值 - 力扣（LeetCode）
class Solution {
public:
vector<double>v;
void BFS(TreeNode* root){
queue<TreeNode*>q;
q.push(root);
while(!q.empty()){
int n=q.size();
long long sum=0.0;
for(int i=0;i<n;++i){
TreeNode* temp=q.front();
sum+=temp->val;
if(temp->left)q.push(temp->left);
if(temp->right)q.push(temp->right);
q.pop();
}
v.push_back(sum*1.0/n);
}
}
vector<double> averageOfLevels(TreeNode* root) {
BFS(root);
return v;
}
};剑指 Offer 32 - II. 从上到下打印二叉树 II - 力扣（LeetCode）
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>>res;
if(root==nullptr)return res;
queue<TreeNode*>q;
q.push(root);
while(!q.empty()){
int n=q.size();
vector<int>temp;
for(int i=0;i<n;++i){
TreeNode* t=q.front();
temp.emplace_back(t->val);
if(t->left)q.push(t->left);
if(t->right)q.push(t->right);
q.pop();
}
res.push_back(temp);
}
return res;
}
};102. 二叉树的层序遍历 - 力扣（LeetCode）
class Solution {
public:
vector<vector<int>>ans;
void BFS(TreeNode* root){
queue<TreeNode*>q;
q.push(root);
while(!q.empty()){
int n=q.size();
vector<int>v;
for(int i=0;i<n;++i){
auto temp=q.front();
v.push_back(temp->val);
if(temp->left)q.push(temp->left);
if(temp->right)q.push(temp->right);
q.pop();
}
ans.push_back(v);
}
}
vector<vector<int>> levelOrder(TreeNode* root) {
if(root==nullptr)return {};
BFS(root);
return ans;
}
};
3.双树相关
101. 对称二叉树 - 力扣（LeetCode）
剑指 Offer 28. 对称的二叉树 - 力扣（LeetCode）
class Solution {
public:
bool check(TreeNode* x,TreeNode* y){
if(x==nullptr && y==nullptr)return true;
if(x==nullptr || y==nullptr)return false;
return x->val==y->val && check(x->left,y->right) && check(x->right,y->left);
}
bool isSymmetric(TreeNode* root) {
return check(root,root);
}
};617. 合并二叉树 - 力扣（LeetCode）
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(root1==nullptr)return root2;
if(root2==nullptr)return root1;
auto newNode=new TreeNode(root1->val+root2->val);
newNode->left=mergeTrees(root1->left,root2->left);
newNode->right=mergeTrees(root1->right,root2->right);
return newNode;
}
};100. 相同的树 - 力扣（LeetCode）
剑指 Offer 27. 二叉树的镜像 - 力扣（LeetCode）
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p==nullptr && q==nullptr)return true;
if(p==nullptr || q==nullptr)return false;
if(p->val!=q->val)return false;
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
};572. 另一棵树的子树 - 力扣（LeetCode）
class Solution {
public:
bool judge(TreeNode* root1,TreeNode* root2){
if(root1==nullptr && root2==nullptr)return true;
if(root1==nullptr || root2==nullptr)return false;
return root1->val==root2->val && judge(root1->left,root2->left) && judge(root1->right,root2->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if(root==nullptr || subRoot==nullptr)return false;
return judge(root,subRoot) || isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}
};235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if((root->val-q->val) * (root->val-p->val)<=0){
return root;
}
return lowestCommonAncestor(p->val<root->val?root->left:root->right,p,q);
}
};236. 二叉树的最近公共祖先 - 力扣（LeetCode）
剑指 Offer 68 - II. 二叉树的最近公共祖先 - 力扣（LeetCode）
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==nullptr)return root;
if(root==p || root==q)return root;
TreeNode* L=lowestCommonAncestor(root->left,p,q);
TreeNode* R=lowestCommonAncestor(root->right,p,q);
if(L==nullptr)return R;
if(R==nullptr)return L;
if(L && R)return root;
return nullptr;
}
};4.树的深度、AVL相关、树的路径
110. 平衡二叉树 - 力扣（LeetCode）
剑指 Offer 55 - II. 平衡二叉树 - 力扣（LeetCode）
class Solution {
public:
int getHeight(TreeNode* root){
if(root==nullptr)return 0;
return max(getHeight(root->left),getHeight(root->right))+1;
}
bool isBalanced(TreeNode* root) {
if(root==nullptr)return true;
return abs( getHeight(root->left) - getHeight(root->right) )<=1 &&
isBalanced(root->left) && isBalanced(root->right);
}
};111. 二叉树的最小深度 - 力扣（LeetCode）
class Solution {
public:
int MIN=INT_MAX;
void DFS(TreeNode* root,int currentDep){
if(root==nullptr){
return;
}
if(root->left==nullptr && root->right==nullptr){
MIN=min(MIN,currentDep);
return;
}
DFS(root->left,currentDep+1);
DFS(root->right,currentDep+1);
}
int minDepth(TreeNode* root) {
if(root==nullptr)return 0;
DFS(root,1);
return MIN;
}
};104. 二叉树的最大深度 - 力扣（LeetCode）
class Solution {
public:
int currentDepth=0;
int maxDep=INT_MIN;
void DFS(TreeNode* root){
if(root==nullptr){
return ;
}
currentDepth++;
maxDep=max(maxDep,currentDepth);
DFS(root->left);
DFS(root->right);
currentDepth--;
}
int maxDepth(TreeNode* root) {
if(root==nullptr)return 0;
DFS(root);
return maxDep;
}
};112. 路径总和 - 力扣（LeetCode）
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if(root==nullptr)return false;
if(root->left==nullptr&&root->right==nullptr){
return targetSum==root->val;
}
return hasPathSum(root->left,targetSum-root->val)||hasPathSum(root->right,targetSum-root->val);
}
};257. 二叉树的所有路径 - 力扣（LeetCode）
class Solution {
public:
void DFS(TreeNode*root,string s,vector<string>&ans){
if(root){
s+=to_string(root->val);
if(root->left==nullptr && root->right==nullptr){
ans.push_back(s);
}else{
s+="->";
DFS(root->left,s,ans);
DFS(root->right,s,ans);
}
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string>v;
DFS(root,"",v);
return v;
}
};543. 二叉树的直径 - 力扣（LeetCode）
class Solution {
public:
int ans=1;
int deep(TreeNode* root){
if(root==nullptr){
return 0;
}
int L=deep(root->left);
int R=deep(root->right);
ans=max(ans,L+R+1);//题目中所谓的直径
return max(L,R)+1;//子树的深度
}
int diameterOfBinaryTree(TreeNode* root) {
if(root==nullptr)return 0;
deep(root);
return ans-1;
}
};剑指 Offer 55 - I. 二叉树的深度 - 力扣（LeetCode）
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root==nullptr)return 0;
return max(maxDepth(root->left),maxDepth(root->right))+1;
}
};
5.树的一些trick操作
226. 翻转二叉树 - 力扣（LeetCode）
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root==nullptr){
return nullptr;
}
swap(root->left,root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};404. 左叶子之和 - 力扣（LeetCode）
class Solution {
public:
int sum=0;
void DFS(TreeNode* root){
if(root==nullptr)return;
if(root->left){
if(root->left->left==nullptr && root->left->right==nullptr){
sum+=root->left->val;
}
DFS(root->left);
}
DFS(root->right);
}
int sumOfLeftLeaves(TreeNode* root) {
if(root==nullptr)return 0;
DFS(root);
return sum;
}
};
6.二叉搜索树BST
利用好BST的中序遍历是一个有序序列的特征，由此可利用二分操作，不论是从小到大还是从大到小。
108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）
面试题 04.02. 最小高度树 - 力扣（LeetCode）
class Solution {
public:
TreeNode* helper(vector<int>& nums,int left,int right){
if(left>right){
return nullptr;
}
int mid=(left+right)>>1;
TreeNode* newNode=new TreeNode(nums[mid]);
newNode->left=helper(nums,left,mid-1);
newNode->right=helper(nums,mid+1,right);
return newNode;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return helper(nums,0,nums.size()-1);
}
};501. 二叉搜索树中的众数 - 力扣（LeetCode）
class Solution {
public:
TreeNode* pre=nullptr;
vector<int>ans;
int cnt=0;
int maxCount=INT_MIN;
void DFS(TreeNode* root){
if(root==nullptr)return;
DFS(root->left);
if(pre==nullptr){
cnt=1;
}else if(pre->val==root->val){
cnt++;
}else{
cnt=1;
}
pre=root;
if(cnt==maxCount){
ans.push_back(root->val);
}
if(cnt>maxCount){
maxCount=cnt;
ans.clear();
ans.push_back(root->val);
}
DFS(root->right);
}
vector<int> findMode(TreeNode* root) {
DFS(root);
return ans;
}
};653. 两数之和 IV - 输入 BST - 力扣（LeetCode）
class Solution {
public:
unordered_set<int>m;
bool findTarget(TreeNode* root, int k) {
if(root==nullptr)return false;
if(m.count(k-root->val)==1){
return true;
}
m.insert(root->val);
return findTarget(root->left,k) || findTarget(root->right, k);
}
};700. 二叉搜索树中的搜索 - 力扣（LeetCode）
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if(root==nullptr)return nullptr;
if(val==root->val){
return root;
}
return val<root->val?searchBST(root->left, val):searchBST(root->right,val);
}
};剑指 Offer 54. 二叉搜索树的第k大节点 - 力扣（LeetCode）
class Solution {
public:
int ans;
void InOrder(TreeNode* root,int &k){
if(root==nullptr)return;
InOrder(root->right,k);
--k;
if(k==0)ans=root->val;
InOrder(root->left,k);
}
int kthLargest(TreeNode* root, int k) {
if(root==nullptr)return 0;
InOrder(root,k);
return ans;
}
};
7.优先队列（TopK，堆排序）
703. 数据流中的第 K 大元素 - 力扣（LeetCode）
class KthLargest {
public:
int k;
priority_queue<int,vector<int>,greater<int>>q;
KthLargest(int k, vector<int>& nums) {
this->k=k;
for(auto &i:nums){
add(i);
}
}
int add(int val) {
q.push(val);
if(q.size()>k){
q.pop();
}
return q.top();
}
};
边栏推荐
- A simple calculation method of vanishing point
- PCB线路板蛇形布线要注意哪些问题？
- Is it safe to buy stocks and open an account on the account opening link of the securities manager? Ask the great God for help
- openssl客户端编程：一个不起眼的函数导致的SSL会话失败问题
- [cloud based co creation] the "solution" of Digital Travel construction in Colleges and Universities
- 国际数字经济学院、华南理工 | Unified BERT for Few-shot Natural Language Understanding（用于小样本自然语言理解的统一BERT）
- Bit.Store：熊市漫漫，稳定Staking产品或成主旋律
- 实战回忆录：从Webshell开始突破边界
- 1023 Have Fun with Numbers
- 惊呆！原来 markdown 的画图功能如此强大！
猜你喜欢
Minmei new energy rushes to Shenzhen Stock Exchange: the annual accounts receivable exceeds 600million and the proposed fund-raising is 450million
Mathematical derivation from perceptron to feedforward neural network
Buzzer experiment based on stm32f103zet6 library function
爬取国家法律法规数据库
Bit.Store：熊市漫漫，稳定Staking产品或成主旋律
429-二叉树（108. 将有序数组转换为二叉搜索树、538. 把二叉搜索树转换为累加树、 106.从中序与后序遍历序列构造二叉树、235. 二叉搜索树的最近公共祖先）
在线文本按行批量反转工具
International School of Digital Economics, South China Institute of technology 𞓜 unified Bert for few shot natural language understanding
昱琛航空IPO被终止：曾拟募资5亿 郭峥为大股东
今晚战码先锋润和赛道第2期直播丨如何参与OpenHarmony代码贡献
随机推荐
新中大冲刺科创板：年营收2.84亿 拟募资5.57亿
1030 Travel Plan
labelimg使用指南
谈谈线程安全
中金证券经理给的开户二维码安全吗？找谁可以开户啊？
Code and principle of RANSAC
Blink SQL内置函数大全
shell脚本常用命令（三）
如何利用 RPA 实现自动化获客？
广发期货开户安全吗？
实战回忆录：从Webshell开始突破边界
基于STM32F103ZET6库函数外部中断实验
Implementation of reliable distributed locks redlock and redisson
Garbage collector driving everything -- G1
Market status and development prospect forecast of the global shuttleless air jet loom industry in 2022
Market status and development prospect forecast of global active quality control air sampler industry in 2022
使用logrotate对宝塔的网站日志进行自动切割
Solution to Maxwell error (MySQL 8.x connection)
maxwell 报错（连接为mysql 8.x）解决方法
ABAP随笔-EXCEL-3-批量导入(突破标准函数的9999行)