前言
企图通过9个习题，拿捏树的一些解题门道。通过本文：
① 可以重温树的前序、中序、后序遍历。
② 切实捋清楚递归的逻辑。
第一题、2236. 判断根结点是否等于子结点之和
题目描述
解题报告
啊，可爱水题~
参考代码(C++版本)
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool checkTree(TreeNode* root) { return root->val == (root->left->val + root->right->val); } };
第二题、 面试题 04.10. 检查子树
本质层序遍历
题目描述
解题报告
其实第一想法了，是将数据哈希，然后比较树T1中出现的数值是否大于等于子树T2中出现的数值。
先放递归的玩法吧，老老实实，能Ac再去玩花的。
参考代码(C++版本)
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool checkSubTree(TreeNode* t1, TreeNode* t2) { //既是特判，也是待会递归的基线条件 if(t2 == NULL) return true; if(t1 == NULL) return false; //然后逐层比较吧 //倘若当前层相同，就递归进去比较各自的左右子树 if(t2->val == t1->val) { //既然要递归，回去补充递归的边界条件，看谁为NULL的时候为真为假 return (checkSubTree(t1->left,t2->left) && checkSubTree(t1->right,t2->right)); } else //否则比较，是不是t1的子树的值了 return (checkSubTree(t1->left,t2) || checkSubTree(t1->right,t2)); } };
第三题 面试题 04.06. 后继者
本质中序遍历
题目描述
解题报告
题目中说了，要我们去找当前结点的一下个，也就是中序遍历的后继，那么就安装中序遍历去递归，即找到目标结点之后了，递归进右子树，也就是其后继结点中去找答案。
总体来说，也就是英雄哥阐述的这种了。
参考代码(C++版本)
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* ans; bool flag; void dfs(TreeNode* root_dfs, TreeNode* p) { if(root_dfs == NULL) return; //按照中序搜 //处理左子树 dfs(root_dfs->left,p); //处理当前的结点，是在找到p结点，并且是后继的情况下 if(flag && !ans) ans = root_dfs; if(root_dfs == p) flag = true;//找到p这个结点了，标记它，待会要进行的是搜右子树，也就是找它的后继。 //处理右子树，也就是进去找后继结点 dfs(root_dfs->right,p); } TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) { //按照题目的意思去搜索吧，找中序遍历的后继。 //中序遍历是左子树、根、右子树 flag = false;//标记是否找到结点p了 ans = NULL; dfs(root,p); return ans; } };
第四题 1110. 删点成林
本质后序遍历 + bool标记
题目描述
解题报告
题目是对后序遍历的变型。
为什么这么说了，因为要求我们把需要删除的结点的子树统计起来。那么整体的逻辑应该是，处理左右子树，再回到根判断当前的结点是不是需要删除的结点了。倘若是，那么就将左右子树存储到返回结果的集合中。
那么这个大流程就是左子树、右子树、根。也就是后序遍历了，我们在递归的时候也按照这种大逻辑进行，各个小的板块，也会践行这种逻辑的，最终自顶向下的搜索，自底向上的回溯结果。
参考代码(C++版本)
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int hash[1010];//统计要删除结点的一个哈希表 vector<TreeNode*> ans; void dfs(TreeNode* father,bool falg_left, TreeNode* node) { //设置递归的边界 if(node == nullptr) return; //按照后序遍历去扫描 dfs(node,true,node->left); dfs(node,false,node->right); //找到需要删除的结点了 if(hash[node->val] == 1) { if(father)//倘若它有父结点，就需要父结点断开链接 { //通过标记判断有没有左右子树 if(falg_left) father->left = nullptr; else father->right = nullptr; } //将需要删除的结点root不使用了，其子树的现在单独成树 if(node->left) ans.push_back(node->left); if(node->right) ans.push_back(node->right); } } vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) { //姑且可以理解为，类似后序遍历。找到要删除的结点（也可以说它是父结点），看其左右子树存在与否 if(root == nullptr) return {}; ans.clear(); memset(hash,0,sizeof(hash)); int n = to_delete.size(); for(int i = 0; i < n;i++) hash[to_delete[i]] ++; //搜索并统计符合要求的结果 //三个参数分别是，当前结点的父结点(用于和删除结点断开)、左子树的标记、当前的结点。 dfs(nullptr,false,root); //判断最初的根节点形成的树是否被动过，倘若没有。加入结果集，形成子树 if(hash[root->val] == 0) ans.push_back(root); return ans; } };
这个标记的思想，和前面的一个dijkstra习题很像，都是因为搜索的落实都是一致，只是有细微的区别，比如现在是搜左子树和右子树，之前的dijkstra是搜索的出发和回来。本题是可以放一个bool 标记，之前的这个题是放置的偏移量，本质都是相同逻辑的再运用。
第五题 P1629 邮递员送信
题目描述
解题报告
我自己是图论废物，题目意思倒是能get到：邮递员先去取，取了再拿回邮局，问最短时间，也就是求最短路径吧。
关于最短路
最短路的概念阐释我直接去薅的 引用的执梗的文章，需要的小伙伴可以自行点击链接，跳转到原文嗷~
零基础学算法100天第1天——Dijkstra（图解最短路算法）
Dijkstra算法目前是有两个版本，一种是朴素版本，用于稠密图，一种是堆优化版本，用于稀疏图。英雄哥的建议值着重掌握堆优化版本。
下面放的算法板子，完全来自acwing中闫总的总结，想看原文档的小伙伴也可以自行点击实现跳转：
acwing
朴素dijkstra算法
Q：① 什么是稠密图？
A：稠密图是题目给的数据点比较小，比如几十个点，或者几百个点，一般不会上千的，同时有上万条边，比如下图中的数据范围：
对于这张图整体而言，是比较稠密的，使用一个二维数组来存储(一般称呼为邻接矩阵)的效果就很好。
此时使用的就是这张算法板子，权当了解吧，辅助记忆下面堆优化版本的板子，
闫总代码中的注释也挺详细的了，我就不赘述啦
堆优化版dijkstra
需要使用堆优化版本的dijkstra 的数据范围大致是这种的，点和边差不多一样多，这种时候使用邻接矩阵来存储了，就十分浪费空间，因此考虑使用邻接表来存储(一般使用数组实现，结合数据结构中链表的思想来模拟)
也是直接放闫总的板子了，然后关于存储点，不一定需要使用pair，用结构体也是可以的，哪个舒服又能Ac就用哪个。
浅复习了一下知识点，那咱们看看这个题，大佬们是怎么解决的了。因为邮递员有出去的动作，还有回来的过程，按照题意理解了，确实需要两遍最短路算法。
参考代码(C++版本)
#include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long LL; typedef pair<int,int> PII; const int N = 1010 , M = 2e5 + 10; int n,m; LL ans; int h[N*2],e[M],ne[M],w[M],idx;//用邻接表存储所有的边的信息 int dist[N];//存所有点到1号点的距离 bool vis[N];//存储每个点的最短路径是否已经确定了 //构建邻接表的板子 void add(int a,int b,int c) { e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++; } //传入的参数是偏移量，决定是否是反向图 void dijkstra(int d) { memset(vis,0,sizeof vis);//都标记为没有探索过 memset(dist,0x3f,sizeof dist);//将距离数组初始化为正无穷 //初始化一步dist数组，dist[1] = 0; dist[1] = 0; priority_queue<PII,std::vector<PII>,greater<>> heap;//大根堆：按照first从大到小排序，背过 heap.push({0,1+d}); //有点像BFS 了，队头不空，取队头，拓展队头 while(heap.size()) { auto t = heap.top(); heap.pop(); int var = t.y; if(vis[var-d]) continue; vis[var-d] = true; //用当前探索的结果来拓展 for(int i = h[var];i != -1;i = ne[i]) { int j = e[i]; if(!vis[j-d] && dist[j-d] > dist[var-d] + w[i])//更新最短路 { dist[j-d] = dist[var-d] + w[i]; heap.push({dist[j-d],j}); } } } } int main(int argc, char const *argv[]) { //输入环节 cin >> n >> m; //初始化邻接表 memset(h,-1,sizeof h); //按照题目意思构建m条边的图 for(int i = 1;i <= m;i++) { int a,b,c; cin >> a >> b >>c; //因为每条路是单行独立的，因此需要构建出去和回来的图。 add(a,b,c),add(b+N,a+N,c); } //扫一遍出去取的最小路径 dijkstra(0); for(int i = 2; i <= n;i++) ans += dist[i]; //扫一遍取完回来的 dijkstra(N); for(int i = 2;i <= n;i++) ans += dist[i]; cout << ans; return 0; }
第六题 144. 二叉树的前序遍历
题目描述
解题报告
在根节点存在的情况下，存根节点的信息，递归进左子树、右子树。
参考代码(C++版本)
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> ans; vector<int> preorderTraversal(TreeNode* root) { //在根节点存在的情况下，根左右 if(root) { ans.push_back(root->val); preorderTraversal(root->left); preorderTraversal(root->right); } return ans; } };
第七题 94. 二叉树的中序遍历
题目描述
解题报告
换汤不换药，水题嘎嘎乱杀~
参考代码(C++版本)
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> ans; vector<int> inorderTraversal(TreeNode* root) { if(root) { inorderTraversal(root->left); ans.push_back(root->val); inorderTraversal(root->right); } return ans; } };
第八题 145. 二叉树的后序遍历
题目描述
解题报告
参考代码(C++版本)
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> ans; vector<int> postorderTraversal(TreeNode* root) { if(root) { postorderTraversal(root->left); postorderTraversal(root->right); ans.push_back(root->val); } return ans; } };
第九题 104. 二叉树的最大深度
递归
题目描述
解题报告
参考代码(C++版本)
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int maxDepth(TreeNode* root) { if(root == nullptr) return 0; //也是直接递归解决吧 //统计左右子树的最大值+1 return max(maxDepth(root->left),maxDepth(root->right))+1; } };
总结
① 递归是先自顶向下的搜索，当到达了可以求解的位置，再带着解慢慢回溯回来。那么我就考虑最大的板块的逻辑就好，其他小的板块是和现在的逻辑一样的。
比如最后一题求二叉树的最大深度，那么整体的逻辑就是求左子树和右子树的最大深度。再补加上根这层的深度1。
那么整个代码会递归进去按照同样的逻辑处理：在左子树和右子树中也做类似的操作，最后回溯回来的，其实就是各个子树的最大深度。
回溯到根root这儿的时候，就是最初始表示的，左子树的最大深度和右子树的最大深度。
② 搜索不应该被限定在哪儿可以用，万物皆可搜，更何况是对于搜索的源泉——树
