2.8
1.二叉树的前序遍历
2.二叉树的中序遍历
3.二叉树的后序遍历
4.⼆叉树的层序遍历
5.⼆叉树的层序遍历2
6.二叉树的右视图
7.二叉树的层平均值
8.N叉树的层序遍历
9.每个树行中找最大值
10.填充每个节点的下一个右侧节点指针
11.填充每个节点的下一个右侧节点指针2
12.生命之树（树状DP）
13.最大子树和
14.没有上司的舞会
15.对称二叉树
16.完全二叉树的节点个数
17.二叉树的最大深度
18.二叉树的最小深度
19.翻转二叉树
二叉树的前序遍历：https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
class Solution {
public:
void Traversal(TreeNode *cur,vector<int>&a){
if (cur==NULL) return;
a.push_back(cur->val);
Traversal(cur->left,a);
Traversal(cur->right,a);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int>a;
Traversal(root,a);
return a;
}
};二叉树的中序遍历https://leetcode.cn/problems/binary-tree-inorder-traversal/description/
class Solution {
public:
void traversal(TreeNode *cur,vector<int>&a){
if (cur==NULL)return ;
traversal(cur->left,a);
a.push_back(cur->val);
traversal(cur->right,a);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int>a;
traversal(root,a);
return a;
}
};二叉树的后序遍历https://leetcode.cn/problems/binary-tree-postorder-traversal/description/
class Solution {
public:
void traversal(TreeNode *cur,vector<int>&a){
if (cur==NULL) return;
traversal(cur->left,a);
traversal(cur->right,a);
a.push_back(cur->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int>a;
traversal(root,a);
return a;
}
};⼆叉树的层序遍历https://leetcode.cn/problems/binary-tree-level-order-traversal/description/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*>que;
if (root!=NULL) que.push(root);
vector<vector<int> >res;
while(!que.empty()){
int size=que.size();
vector<int>a;
for (int i=0;i<size;++i){
TreeNode* node=que.front(); que.pop();
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
a.push_back(node->val);
}
res.push_back(a);
}
return res;
}
};⼆叉树的层序遍历2https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/description/
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
queue<TreeNode*>q;
if (root!=NULL) q.push(root);
vector<vector<int> >res;
while (!q.empty()){
int size=q.size();
vector<int>a;
for (int i=0;i<size;++i){
TreeNode* now=q.front(); q.pop();
if (now->left) q.push(now->left);
if (now->right) q.push(now->right);
a.push_back(now->val);
}
res.push_back(a);
}
reverse(res.begin(),res.end());
return res;
}
};二叉树的右视图https://leetcode.cn/problems/binary-tree-right-side-view/
思路：标记每一层的最后一个节点
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
queue<TreeNode*>q;
vector<int>res;
if (root!=NULL)q.push(root);
int d=0;
while (!q.empty()){
int size=q.size();
vector<int>a;
d++;
for (int i=0;i<size;++i){
TreeNode* cur=q.front(); q.pop();
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
if (i==size-1) res.push_back(cur->val);
}
}
return res;
}
};二叉树的层平均值https://leetcode.cn/problems/average-of-levels-in-binary-tree/description/
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double>res;
queue<TreeNode*>q;
if (root!=NULL) q.push(root);
while (!q.empty()){
int size=q.size();
double sum=0.0;
for (int i=0;i<size;++i){
TreeNode* node=q.front(); q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
sum+=node->val;
}
res.push_back(sum/size);
}
return res;
}
};N叉树的层序遍历https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
queue<Node*>q;
vector<vector<int> >res;
if (root!=NULL) q.push(root);
while (!q.empty()){
int size=q.size();
vector<int>a;
for (int i=0;i<size;++i){
Node* node=q.front(); q.pop();
a.push_back(node->val);
for (int i=0;i<node->children.size();++i){
if (node->children[i]) q.push(node->children[i]);
}
}
res.push_back(a);
}
return res;
}
};每个树行中找最大值https://leetcode.cn/problems/find-largest-value-in-each-tree-row/description/
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
queue<TreeNode*>q;
vector<int>res;
if (root!=NULL) q.push(root);
while (!q.empty()){
int size=q.size();
int maxn=INT_MIN;
for (int i=0;i<size;++i){
TreeNode* node=q.front(); q.pop();
maxn=max(maxn,node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
res.push_back(maxn);
}
return res;
}
};填充每个节点的下一个右侧节点指针https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/description/
class Solution {
public:
Node* connect(Node* root) {
queue<Node*>q;
if (root!=NULL) q.push(root);
while (!q.empty()){
int size=q.size();
Node* nodepre;
Node* node;
for (int i=0;i<size;++i){
if(i==0){
nodepre=q.front(); q.pop();
node=nodepre;
}else{
node=q.front(); q.pop();
nodepre->next=node;
nodepre=node;
}
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
nodepre->next=NULL;
}
return root;
}
};填充每个节点的下一个右侧节点指针2https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/description/
class Solution {
public:
Node* connect(Node* root) {
queue<Node*>q;
if (root!=NULL) q.push(root);
while (!q.empty()){
int size=q.size();
Node* nodepre;
Node* node;
for (int i=0;i<size;++i){
if(i==0){
nodepre=q.front(); q.pop();
node=nodepre;
}else{
node=q.front(); q.pop();
nodepre->next=node;
nodepre=node;
}
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
nodepre->next=NULL;
}
return root;
}
};二叉树的最大深度https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/
class Solution {
public:
int maxDepth(TreeNode* root) {
queue<TreeNode*>q;
vector<int>res;
if (root!=NULL)q.push(root);
int d=0;
while (!q.empty()){
int size=q.size();
vector<int>a;
d++;
for (int i=0;i<size;++i){
TreeNode* cur=q.front(); q.pop();
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
if (i==size-1) res.push_back(cur->val);
}
}
return d;
}
};二叉树的最小深度https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/
class Solution {
public:
int minDepth(TreeNode* root) {
queue<TreeNode*>q;
vector<int>res;
if (root!=NULL)q.push(root);
int d=0;
while (!q.empty()){
int size=q.size();
vector<int>a;
d++;
for (int i=0;i<size;++i){
TreeNode* cur=q.front(); q.pop();
bool flag1=false,flag2=false;
if (cur->left) q.push(cur->left);
else flag1=true;
if (cur->right) q.push(cur->right);
else flag2=true;
if (flag1 && flag2) return d;
}
}
return 0;
}
};翻转二叉树https://leetcode.cn/problems/invert-binary-tree/description/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
queue<TreeNode*>q;
if (root!=NULL)q.push(root);
while (!q.empty()){
int size=q.size();
for (int i=0;i<size;++i){
TreeNode* cur=q.front(); q.pop();
swap(cur->left,cur->right);
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
}
return root;
}
};对称二叉树https://leetcode.cn/problems/symmetric-tree/
class Solution {
public:
bool compare(TreeNode* left,TreeNode * right){
if (left==NULL && right==NULL) return true;
else if (left!=NULL && right==NULL) return false;
else if (left==NULL && right!=NULL) return false;
else if (left->val !=right->val) return false;
return compare(left->left,right->right) && compare(left->right,right->left);
}
bool isSymmetric(TreeNode* root) {
return compare(root->left,root->right);
}
};完全二叉树的节点个数https://leetcode.cn/problems/count-complete-tree-nodes/description/
class Solution {
public:
int countNodes(TreeNode* root) {
queue<TreeNode*>q;
int cnt=0;
if (root!=NULL)q.push(root);
while (!q.empty()){
int size=q.size();
for (int i=0;i<size;++i){
TreeNode* node=q.front(); q.pop();
cnt++;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return cnt;
}
};
生命之树https://www.luogu.com.cn/problem/P8625
题目描述
在 X 森林里，上帝创建了生命之树。
他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。
上帝要在这棵树内选出一个节点集合 �S（允许为空集），使得对于 �S 中的任意两个点 �,�a,b，都存在一个点列 �,�1,�2,⋯ ,��,�a,v1,v2,⋯,vk,b 使得这个点列中的每个点都是 �S 里面的元素，且序列中相邻两个点间有一条边相连。
在这个前提下，上帝要使得 �S 中的点所对应的整数的和尽量大。
这个最大的和就是上帝给生命之树的评分。
经过 atm 的努力，他已经知道了上帝给每棵树上每个节点上的整数。但是由于 atm 不擅长计算，他不知道怎样有效的求评分。他需要你为他写一个程序来计算一棵树的分数。
输入格式
第一行一个整数 �n 表示这棵树有 �n 个节点。
第二行 �n 个整数，依次表示每个节点的评分。
接下来 �−1n−1 行，每行 22 个整数 �,�u,v，表示存在一条 �u 到 �v 的边。由于这是一棵树，所以是不存在环的。
输出格式
输出一行一个数，表示上帝给这棵树的分数。
输入输出样例
输入 #1复制
5 1 -2 -3 4 5 4 2 3 1 1 2 2 5输出 #1复制
8说明/提示
对于 30%30% 的数据，�≤10n≤10。
对于 100%100% 的数据，0<�≤105,0<n≤105, 每个节点的评分的绝对值不超过 106106。
时限 3 秒, 256M。
思路：树形DP的板子，主要通过DFS遍历实现，本题的大意主要是从一棵无根树中，求出一个子树，使得所有节点的权值之和最大，主要是通过DFS的方法，以任一节点为根开始DFS
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
const int N=1e5+5;
int dp[N];
vector<int>tree[N];//用邻接表存储图
int res;
void dfs(int u,int fa){
for (int i=0;i<tree[u].size();++i){
int son=tree[u][i];
if (son!=fa){
dfs(son,u);//继续遍历，当前节点作为父亲节点
if (dp[son]>0) dp[u]+=dp[son];
}
}
res=max(res,dp[u]);
}
signed main(){
int n; cin>>n;
for (int i=1;i<=n;++i){ //初始化DP数组
int x; cin>>x;
dp[i]=x;
}
for (int i=0;i<n-1;++i){
int u,v;
cin>>u>>v;
tree[u].push_back(v),tree[v].push_back(u); //构造邻接表，双向边
}
dfs(1,-1);
cout<<res;
}最大子树和https://www.luogu.com.cn/problem/P1122
题目描述
小明对数学饱有兴趣，并且是个勤奋好学的学生，总是在课后留在教室向老师请教一些问题。一天他早晨骑车去上课，路上见到一个老伯正在修剪花花草草，顿时想到了一个有关修剪花卉的问题。于是当日课后，小明就向老师提出了这个问题：
一株奇怪的花卉，上面共连有 �N 朵花，共有 �−1N−1 条枝干将花儿连在一起，并且未修剪时每朵花都不是孤立的。每朵花都有一个“美丽指数”，该数越大说明这朵花越漂亮，也有“美丽指数”为负数的，说明这朵花看着都让人恶心。所谓“修剪”，意为：去掉其中的一条枝条，这样一株花就成了两株，扔掉其中一株。经过一系列“修剪“之后，还剩下最后一株花（也可能是一朵）。老师的任务就是：通过一系列“修剪”（也可以什么“修剪”都不进行），使剩下的那株（那朵）花卉上所有花朵的“美丽指数”之和最大。
老师想了一会儿，给出了正解。小明见问题被轻易攻破，相当不爽，于是又拿来问你。
输入格式
第一行一个整数 � (1≤�≤16000)n (1≤N≤16000)。表示原始的那株花卉上共 �n 朵花。
第二行有 �n 个整数，第 �i 个整数表示第 �i 朵花的美丽指数。
接下来 �−1n−1 行每行两个整数 �,�a,b，表示存在一条连接第 �a 朵花和第 �b 朵花的枝条。
输出格式
一个数，表示一系列“修剪”之后所能得到的“美丽指数”之和的最大值。保证绝对值不超过 21474836472147483647。
输入输出样例
输入 #1复制
7
-1 -1 -1 1 1 1 0
1 4
2 5
3 6
4 7
5 7
6 7输出 #1复制
3
说明/提示
数据范围及约定
对于 60%60% 的数据，有 1≤�≤10001≤N≤1000；
对于 100%100% 的数据，有 1≤�≤160001≤N≤16000。
思路：树形DP
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
const int N=16005;
int dp[N];
vector<int>tree[N];
int res=-2147483647;
void dfs(int u,int fa){
for (int i=0;i<tree[u].size();++i){
int son=tree[u][i];
if (son!=fa){
dfs(son,u);
if (dp[son]>0) dp[u]+=dp[son];
}
}
res=max(dp[u],res);
}
signed main(){
int n;
cin>>n;
for (int i=1;i<=n;++i){
cin>>dp[i];
}
for (int i=0;i<n-1;++i){
int a,b;
cin>>a>>b;
tree[a].push_back(b);
tree[b].push_back(a);
}
dfs(1,-1);
cout<<res;
}没有上司的舞会https://www.luogu.com.cn/problem/P1352
题目描述
某大学有 �n 个职员，编号为 1…�1…n。
他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。
现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 ��ri，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。
所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
输入格式
输入的第一行是一个整数 �n。
第 22 到第 (�+1)(n+1) 行，每行一个整数，第 (�+1)(i+1) 行的整数表示 �i 号职员的快乐指数 ��ri。
第 (�+2)(n+2) 到第 2�2n 行，每行输入一对整数 �,�l,k，代表 �k 是 �l 的直接上司。
输出格式
输出一行一个整数代表最大的快乐指数。
输入输出样例
输入 #1复制
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5输出 #1复制
5
说明/提示
数据规模与约定
对于 100%100% 的数据，保证 1≤�≤6×1031≤n≤6×103，−128≤��≤127−128≤ri≤127，1≤�,�≤�1≤l,k≤n，且给出的关系一定是一棵树。
思路：树形DP，由于存在制约关系，所以增加DP数组的维度，从而来确定状态
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
const int N=16005;
int dp[N][2],w[N];
vector<int>tree[N];
int res=-2147483647;
void dfs(int u,int fa){
dp[u][0]=0;
dp[u][1]=w[u];
for (int i=0;i<tree[u].size();++i){
int son=tree[u][i];
if (son!=fa){
dfs(son,u);
dp[u][0]+=max(dp[son][1],dp[son][0]);
dp[u][1]+=dp[son][0];
}
}
}
signed main(){
int n;
cin>>n;
for (int i=1;i<=n;++i){
cin>>w[i];
}
for (int i=0;i<n-1;++i){
int a,b;
cin>>a>>b;
tree[a].push_back(b);
tree[b].push_back(a);
}
dfs(1,-1);
cout<<max(dp[1][1],dp[1][0]);
}
![【深度学习：SegGPT】在上下文中分割所有内容 [解释]](https://img-blog.csdnimg.cn/direct/0eb8cc0425964117a06894153716420e.png)
