代码随想录训练营第二十三天| 572.另一颗树的子树 104.二叉树的最大深度 559.N叉树的最大深度 111.二叉树的最小深度

572.另一颗树的子树：

状态：已做出

 思路：

这道题目当时第一时间不是想到利用100.相同的树思路来解决，而是先想到了使用kmp，不过这个题目官方题解确实是有kmp解法的，我使用的暴力解法，kmp的大致思路是使用前序遍历整个树的节点，并且要把所有的空子树都考虑进去，不然会出现前序相同树的结构不同的情况，这些节点都放入一个char型数组中，空节点可以任意使用一个字符来表示，做到这一步后就完全是把题目转变为了kmp问题，使用kmp来解决既可，暴力解法的思路:使用和100.相同的树相似的做法，遍历root的每个节点，把每个节点都看成一颗子树，然后这个子树和subRoot使用和100题相同的做法，查看两个树是否相同就能判断出最后的结果了。总体来说暴力解法的时间复杂度是O(n*m)，而kmp的时间复杂度优化到O(n+m)，n和m分别是root和subRoot的节点树。
代码如下:

/*** 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 dfs(TreeNode* root,TreeNode* sub) {if(!root && !sub) return true;if(!root || !sub ||(root->val!=sub->val)) return false;//这里的if语句把三种不相等的情况都包含进去了bool a1=dfs(root->left,sub->left);bool a2=dfs(root->right,sub->right);return a1 && a2;//需要左右子树都为真才说明这两个树相同}//这个函数是用来遍历树的每个节点的，让每个子树都和subRoot判断bool Subreturn(TreeNode* left, TreeNode* right) {bool rusult=dfs(left,right);if(rusult) return true;if(left==nullptr) return false;bool a1=Subreturn(left->left,right);bool a2=Subreturn(left->right,right);return a1 || a2;//使用递归来遍历所有root的节点，最后只要有一处子树和sunRoot相同就符合题意}bool isSubtree(TreeNode* root, TreeNode* subRoot) {if(!root) return false;return Subreturn(root,subRoot);}
};

遇到的困难：

当时做这道题目一开始以为使用100题的思路是优解，所以没想过暴解，就一直在想使用这个思路怎能去优化解决题目，但是发现一直出现问题，因为这道题要优化时间的话必须要考虑判断出错后怎么去回溯，这就让我想到了kmp，随后看完官方的解法后才知道这到题目使用判断相同数的思路就是暴力解法，必须要每个节点都判断才能得到正确答案，官方题解还给出了一种使用哈希树的解法，听着就你难，所以完全看思路。

收获：

这道题目使用判断是否是相同的数的方法就是暴力，通过练习熟悉一下这种解法，做法和之前的100题几乎一样，这道题目跟字符串求是否有相同子串的思想很像。

104.二叉树的最大深度：

文档讲解：代码随想录|104.二叉树的最大深度

视频讲解：二叉树的高度和深度有啥区别？究竟用什么遍历顺序？很多录友搞不懂 | LeetCode：104.二叉树的最大深度_哔哩哔哩_bilibili

状态：已做出

思路：

这下题目之前我使用层序遍历解决过，这次主要是使用前序和后续来解决这代题目。后序的思路:使用后续就是求根结点的最大高度，我的递归结束条件是节点为空时返回0，每次递归设置两个变量，分别保存这个节点的左右子树的层数有多少，最后去这两者的最大值，最后返回最大值加一，按照这个递归思路打到根结点就能返回最大深度。前序思路:前序是求最深的叶子结点深度。和后序递归不同，递归代码的参数我多设计了一个变量n，用来记录此时的层级，在递归到节点为空后返回n结束递归，每层设置两个变量来保存次节点的左右子树的最大深度，然后去这两个变量的最大值，直接返回最大值就可以了。

后序遍历：

/*** 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 dfs(TreeNode* root) {if(root==nullptr) {return 0;//这里返回零是为了从最深的地方开始不断向上回溯来记录高度}int sum1=dfs(root->left);int sum2=dfs(root->right);int n=max(sum1,sum2);//去最大值return ++n;//这里需要把此时的节点考虑进去，所以要加一}int maxDepth(TreeNode* root) {if(!root) return 0;return dfs(root);}
};

前序遍历：

/*** 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 dfs(TreeNode* root,int n) {if(root==nullptr) {return n;//返回n，因为这里空节点不考虑}int sum1=dfs(root->left,n+1);//每次都要让参数加一，记录层级int sum2=dfs(root->right,n+1);int num=max(sum1,sum2);return num;//这里之所以不加一是因为在遍历后序节点的时候num就已经把加一操作包含进去了，比如如果只有根节点的话，最后不加一也返回深度为1}int maxDepth(TreeNode* root) {if(!root) return 0;return dfs(root,0);}
};

遇到的困难：

这道题目使用前后序来做比层序遍历难一点，其中的难点就是难以控制递归的代码，不好记录层级，首先后序我使用递归返回0的方式是为了考虑最后节点为空的那一层，随后使用两个变量分别保存左右子树的最大深度，就是没一层每一层的递归来找到最后根结点的最大深度的，这个点就是是递归抽象的地方，需要由深到浅来思考，不然就会想错，最后返回的最大值我多加了1是为了把这一层考虑进去，因为左右子节点的最大高度都求出了，最后要加上这一次的层级返回。前序递归结束返回n是因为我在每层都讲n累加了，所以直接返回n就行了，下面的两个变量的递归传入n+1就是累加层级，最后和后序一样返回最大值，这里不和后序一样返回最大值加一是因为在左右子树递归后判断的最大值就已经把这一层级考虑进去了，所以直接返回。

收获：

这道题目使用层序遍历比递归方法要简单，主要是层序好理解，递归还是有点抽象，这道题对加深递归理想有一定的帮助，相比前中后序的简单递归，这道题目需要更加了解递归的规则才能合理分配出层级或者高度的改变。

559.N叉树的最大深度 ：

文档讲解：代码随想录|104.二叉树的最大深度

状态：已做出 

思路：

这道题目和上一道求二叉树最大深度一样，我使用了前序后序和层序三种遍历方式去实现了这道题目。这里后序实现最后结束递归是返回的1，因为这里二叉树后序不一样，二叉树可以递归到空节点，但是N叉树不能，所以这里返回后必须要把这一层考虑进去，所以返回放是1，随后的操作二叉树的就差不多了，就是要使用循环来一直遍历一个节点的所有节点，每次循环记比较大小，保存这些节点的最大值，最后好和二叉树思想一样，返回最大值加一。前序则和二叉树放最大深度求法没太大的区别，直接改成循环遍历所有直接点既可。层序遍历相比于递归就简单多了，层序遍历所有节点，记录每层层级最后返回就可以了。

后序遍历：

/*
// Definition for a Node.
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
*/class Solution {
public:int dfs(Node* root) {if(!root->children.size()) return 1;//这里是返回1，因为最后是遇到叶子节点才结束递归，要算上叶子节点int ans=0;//这里和而二叉树不同，需要循环遍历所有子节点。其他和二叉树的思路差不多for(int i=0;i<root->children.size();++i) {int sum=dfs(root->children[i]);ans=max(sum,ans);}return ans+1;//算上此节点层级}int maxDepth(Node* root) {if(!root) return 0;return dfs(root);}
};

前序遍历：

/*
// Definition for a Node.
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
*/class Solution {
public:int dfs(Node* root,int n) {if(!root->children.size()) return n;//这里在递归参数就考虑到了加一的情况，所以直接返回nint ans=0;for(int i=0;i<root->children.size();++i) {int sum=dfs(root->children[i],n+1);ans=max(sum,ans);}return ans;}int maxDepth(Node* root) {if(!root) return 0;return dfs(root,1);}
};

层序遍历：

/*
// Definition for a Node.
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
*/class Solution {
public:int maxDepth(Node* root) {if(!root) return 0;queue<Node*>qu;qu.push(root);int n=0;while(!qu.empty()) {int size=qu.size();++n;//每一层都要加上层级for(int i=0;i<size;++i) {Node* temp=qu.front();qu.pop();for(int j=0;j<temp->children.size();++j) {qu.push(temp->children[j]);}}}return n;}
};

遇到的困难：

这道题目难点就是N叉树有多个节点，需要在递归和层序遍历里面设置一个循环来遍历所有结点，还有一点就是N叉树因为不会递归到空节点，所以后序需要对代码进行一点细节的改善。

收获：

这道题目就是二叉树的进阶，和二叉树的求法没太大区别，练习能进一步理解二叉树的代码思路。

 111.二叉树的最小深度：

文档讲解：代码随想录|111.二叉树的最小深度

视频讲解：看起来好像做过，一写就错！ | LeetCode：111.二叉树的最小深度_哔哩哔哩_bilibili

状态：已做出

思路：

这道题目使用层序我之前做过，这次主要是使用前序和后序的递归来实现，这道题目我觉得使用递归实现起来比求最大深度还要麻烦一点，这里容易出错的问题文档中有明确说明，就是不明确处理叶子结点就会出现误判，比如根结点的左子树为空时，不管右子树是否为空最后出现的最小深度都是1。这道题的具体要求是要我们求根结点到最浅层级的深度有多大，所以递归的结束条件我这里设置的是到叶子节点后结束递归，后序为了考虑这一层所以返回1，前序我这里在递归里设置了一个参数n来记录层级，和二叉树的思路有点点相似，每到一层就n+1。不管是后序还是前序都先设置两个变量，并让变量指向int最大值，因为每次都需要比较取最小值，而且每次递归都要判断此节点做右子树必须是非空才能进行递归，这样是为了不出现考虑空节点层级的情况。
代码如下：

后序遍历：

/*** 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 dfs(TreeNode* root) {if(!root->left && !root->right) return 1;int sum1=INT_MAX,sum2=INT_MAX;//这里先设置两个变量为最大值，因为下面的递归困难会因为子节点为空而不会改变变量的值//这里是为了避免文档所说的错误，所以设置了if语句if(root->left)sum1=dfs(root->left);if(root->right)sum2=dfs(root->right);return min(sum1,sum2)+1;}int minDepth(TreeNode* root) {if(!root) return 0;return dfs(root);}
};

前序遍历：

/*** 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 dfs(TreeNode* root,int n) {if(!root->left && !root->right) return n;//叶子节点就直接返回结束递归int sum1=INT_MAX,sum2=INT_MAX;if(root->left)sum1=dfs(root->left,n+1);if(root->right)sum2=dfs(root->right,n+1);return min(sum1,sum2);}int minDepth(TreeNode* root) {if(!root) return 0;return dfs(root,1);//这里设置为1是直接先把根节点考虑进去了}
};

遇到的困难：

使用层序遍历求最小比求最大要简单，没想到使用递归却相反，求最小反而细节处更多。

收获：

以上这些题目主要都是使用递归去实现的，主要是提升对递归的掌握成程度。