單值二叉樹（力扣）
---------------------------------------------------哆啦A夢的任意門-------------------------------------------------------
我們來看一下題目的具體要求：
?既然我們都學(xué)了二叉樹了，我們就應(yīng)該學(xué)會如何去遞歸。
分析一下：
我們?nèi)绻ビ帽闅v的思路去做，肯定是可以做出來的，遍歷嘛，先將第一次出現(xiàn)的數(shù)給存起來作為一個(gè)key，那么遍歷整個(gè)二叉樹，如果出現(xiàn)了一個(gè)不同于這個(gè)key的數(shù)值，那么我們就說這個(gè)二叉樹不是單值二叉樹，如果到最后訪問完整個(gè)二叉樹都沒有出現(xiàn)一個(gè)不同于這個(gè)key的值，那么我們就可以說這個(gè)二叉樹是一個(gè)單值二叉樹。
但是看了一下這個(gè)思路，一個(gè)個(gè)遍歷是不是顯得十分的齪??？
那么我們就要用二叉樹獨(dú)特的特點(diǎn)，根和它的左子樹和右子樹進(jìn)行對比，以此來遞歸。
我們是不是就突然之間就想出做法了呢？
那么思路如下：
用根的值和左子樹和右子樹的值進(jìn)行對比。如果出現(xiàn)一次不相同就可以返回false了。
bool isUnivalTree(struct TreeNode* root){
if(root == NULL)
{
return true;
}
if(root->left != NULL && root->left->val != root->val)
{
return false;
}
if(root->right != NULL && root->right->val != root->val)
{
return false;
}
return isUnivalTree(root->left) && isUnivalTree(root->right);
}? 只要遇到底層的NULL，我們直接返回true，因?yàn)橹灰霈F(xiàn)左子樹或右子樹返回了一個(gè)false，整個(gè)二叉樹就不是單值二叉樹了。所以用&&運(yùn)算符。
二叉樹最大深度（力扣）
---------------------------------------------------哆啦A夢的任意門-------------------------------------------------------
來看一下題目要求：
二叉樹是由根-左子樹-右子樹構(gòu)成的，所以如果要知道二叉樹的最大深度，我們就去找到左子樹和右子樹當(dāng)中最深的那棵樹的具體深度 + 1就是我們這棵樹的最大深度了。
那么出現(xiàn)遞歸結(jié)束的條件也是很簡單啊，就是我們訪問的一個(gè)根，這個(gè)根如果是空的，我們就可以返回0，別問我為什么不返回1，空的為啥要返回1？
所以來看代碼叭~
int maxDepth(struct TreeNode* root){
if(root == NULL)
{
return 0;
}
int left = maxDepth(root->left);
int right = maxDepth(root->right);
if(left < right)
{
return 1 + right;
}
return 1 + left;
}翻轉(zhuǎn)二叉樹（力扣）
---------------------------------------------------哆啦A夢的任意門-------------------------------------------------------
還是來看一下題目要求~
光看這個(gè)題目完全不懂它的意思，但是一看這個(gè)圖就明白了。
我們就是需要讓一個(gè)根的兩個(gè)子樹翻轉(zhuǎn)過來，讓一個(gè)根的左子樹作為它的右子樹，它的右子樹作為它的左子樹。
那么思路就很清晰了，我們的遞歸結(jié)束條件就是當(dāng)遇到空的時(shí)候，我們就返回該結(jié)點(diǎn)。
直接來看代碼叭~
void swap(struct TreeNode** x1,struct TreeNode** x2)
{
struct TreeNode* tmp = *x1;
*x1 = *x2;
*x2 = tmp;
}
struct TreeNode* invertTree(struct TreeNode* root){
if(root == NULL)
{
return root;
}
swap(&(root->left),&(root->right));
invertTree(root->left);
invertTree(root->right);
return root;
}如上，我們寫了一個(gè)交換函數(shù)，但是和平時(shí)的交換函數(shù)好像不太一樣啊，為什么這個(gè)指針是個(gè)二級指針。我們回到這個(gè)翻轉(zhuǎn)二叉樹的函數(shù)當(dāng)中，我們發(fā)現(xiàn)傳進(jìn)去的是root->left和root->right，我們發(fā)現(xiàn)這傳進(jìn)去的是一個(gè)指針。我們需要改變一個(gè)指針，就需要傳入一個(gè)指針的指針，也就是二級指針，所以，這就是為什么這個(gè)交換函數(shù)的兩個(gè)形參是兩個(gè)二級指針。
檢查兩顆樹是否相同（力扣）
---------------------------------------------------哆啦A夢的任意門-------------------------------------------------------
看題目的要求：
分析一下：
結(jié)果為false的幾種可能：
1.對比某個(gè)結(jié)點(diǎn)時(shí)，我們發(fā)現(xiàn)這兩個(gè)結(jié)點(diǎn)的值不是相等的，那么返回false
2.其中一棵二叉樹先遇到了NULL，而另一棵樹還沒遇到NULL，那么返回false
如果對應(yīng)的值相等，而且同時(shí)出現(xiàn)遇到了NULL，那么我們就返回true。
所以來看代碼：
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
if(p == NULL && q == NULL)
{
return true;
}
//若p和q同時(shí)都為NULL，就早已return了
if(p == NULL || q == NULL)
{
return false;
}
if(p->val != q->val)
{
return false;
}
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}對稱二叉樹（力扣）
---------------------------------------------------哆啦A夢的任意門-------------------------------------------------------
看題：
?
我們來觀察一下，根只有一個(gè)，肯定是對稱的啦，它的兩個(gè)左右孩子都是相等的，也就是對稱的。那么再看它的兩個(gè)左右孩子的左右孩子，我們可以發(fā)現(xiàn)，如果要讓這兩個(gè)子樹對稱，那么就需要讓這棵左子樹的右子樹等于右子樹的左子樹，左子樹的左子樹等于右子樹的右子樹。
思路：
判斷一個(gè)樹是否對稱，首先要判斷左右孩子是否對稱相等，還需要判斷左孩子的左子樹是否和右孩子的右子樹對稱，左孩子的右子樹是否和右孩子的左子樹對稱。
bool check(struct TreeNode* p,struct TreeNode* q)
{
if(p == NULL && q == NULL)
return true;
if(p == NULL || q == NULL)
return false;
return p->val == q->val && check(p->left,q->right) && check(p->right, q->left);
}
bool isSymmetric(struct TreeNode* root){
return check(root->left,root->right);
}如果同時(shí)為NULL，那么就返回true，如果出現(xiàn)其中一個(gè)出現(xiàn)了NULL，另一個(gè)沒有出現(xiàn)NULL，那么直接返回false
另一顆樹的子樹（力扣）
---------------------------------------------------哆啦A夢的任意門-------------------------------------------------------
先來看一下題目的要求：
?
這個(gè)像不像上面的有一道題？那道比較兩個(gè)樹是否相等的題。
其實(shí)對比兩個(gè)樹是否相等的思路是一樣的，只不過我們要找到是否這棵子樹是否存在于另一棵樹當(dāng)中。
我們是不是先去root找到一個(gè)與subRoot的根節(jié)點(diǎn)一樣的結(jié)點(diǎn)呢？
之后往下比較兩棵樹是否相等就好了？
那么我們還是從根出發(fā)，去它的左子樹和右子樹去尋找這一棵能和subRoot能完全吻合的子樹。
如果在左子樹找不著，那就去右子樹找，如果都找不到，那么就只能返回一個(gè)false了
來看代碼：
bool isSame(struct TreeNode* s, struct TreeNode* t)
{
if(!s && !t)
return true;
if(!s || !t)
return false;
if(s->val != t->val)
return false;
return isSame(s->left,t->left) && isSame(s->right,t->right);
}
bool isSubtree(struct TreeNode* s, struct TreeNode* t) {
if(!s)
return false;
if(isSame(s,t))
return true;
return isSubtree(s->left,t) || isSubtree(s->right,t);
}從這段代碼，我們的思路還是比較清晰的。文章來源：http://www.zghlxwxcb.cn/news/detail-411223.html
我們從根出發(fā)，先看看這個(gè)根開始，能不能與這棵子樹吻合，如果不吻合就繼續(xù)往下走，結(jié)束的條件也就是我們遇到了NULL，說明這個(gè)根已經(jīng)到了底下了，不可能再有結(jié)點(diǎn)了，直接返回來。文章來源地址http://www.zghlxwxcb.cn/news/detail-411223.html
到了這里，關(guān)于二叉樹（OJ）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
