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是直接先把根節點考慮進去了}
};

遇到的困難：

使用層序遍歷求最小比求最大要簡單，沒想到使用遞歸卻相反，求最小反而細節處更多。

收獲：

以上這些題目主要都是使用遞歸去實現的，主要是提升對遞歸的掌握成程度。