有沒有一起拼用銀行卡的，取錢的時(shí)候我用，存錢的時(shí)候你用

1、相同的樹

難度等級(jí)：?
直達(dá)鏈接：相同的樹

2、單值二叉樹

難度等級(jí)：?
直達(dá)鏈接：單值二叉樹

3、對(duì)稱二叉樹

難度等級(jí)：??
直達(dá)鏈接：對(duì)稱二叉樹

4、二叉樹的前序遍歷

難度等級(jí)：???
直達(dá)鏈接：二叉樹的前序遍歷

5、另一顆樹的子樹

難度等級(jí)：????
直達(dá)鏈接：另一顆子樹
–?–?–?–?–?–?–?–?–?–?–?–?–?–?–?-正文開始-?–?–?–?–?–?–?–?–?–?–?–?–?–?–?–

1、相同的樹

直達(dá)鏈接：相同的樹
題目：
解題思路：

判斷兩個(gè)二叉樹是否相同，而二叉樹又分為根和左右子二叉樹，左右子二叉樹也可以再分（有的話），即需要判斷根是否相同，相同再繼續(xù)比較左右子樹，比較左右子樹也是需要判斷根是否相同，相同的話繼續(xù)向下比較，這就比較適合用遞歸來進(jìn)行解題。

那么下面我們就需要找最小子問題，也就是判斷遞歸終止的條件，這里我們需要考慮到空指針的問題

1.傳過來的兩個(gè)形參可能都是空指針，那么直接返回true

2.而也可能有一個(gè)為空，那么就返回false

3.兩個(gè)都不為空比較數(shù)值是否相等即可

解題代碼：

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//兩個(gè)指針都為空if(p == NULL && q == NULL){return true;}//其中有一個(gè)為空if(p == NULL || q == NULL){return false;}//兩個(gè)指針都不為空if(p->val != q->val){return false;}return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

這里以下面兩個(gè)二叉樹給大家進(jìn)行代碼遞歸圖解，其他的大家可以自行動(dòng)手，有利于加深理解
代碼遞歸圖解：

2、單值二叉樹

直達(dá)鏈接：單值二叉樹
題目：
解題思路：

這道題并不難，還是依照老套路進(jìn)行遞歸遍歷，比較根和子節(jié)點(diǎn)的值，不相等就返回false，相等就繼續(xù)想向下進(jìn)行遞歸（有的話），再比較根和子節(jié)點(diǎn)。。。

那么我們還需要考慮一個(gè)遞歸最小子問題，所傳的形參為空指針的情況，形參為空指針也分兩種情況：

1.開始所傳的就是空指針
2.遞歸到葉節(jié)點(diǎn)的子節(jié)點(diǎn)

這兩種情況都直接返回true即可。

解題代碼：

bool isUnivalTree(struct TreeNode* root) {//根為空if(root == NULL){return true;}//根不為空if(root->left && root->val != root->left->val){return false;}if(root->right && root->val != root->right->val){return false;}return isUnivalTree(root->left) && isUnivalTree(root->right);
}

我們以下面二叉樹舉例進(jìn)行遞歸圖解：

代碼遞歸圖解：
方塊表示調(diào)用該函數(shù)在內(nèi)存上所開辟的空間，圓表示訪問子節(jié)點(diǎn)的數(shù)值。

3、對(duì)稱二叉樹

直達(dá)鏈接：對(duì)稱二叉樹
題目：
解題思路：

這道OJ題讀完題目再看所給的函數(shù)接口大家可能就一頭霧水了。
函數(shù)中所傳的形參只有一個(gè)二叉樹的指針。
而我們要進(jìn)行對(duì)稱判斷的話是必須左右子樹同時(shí)進(jìn)行遞歸到相應(yīng)位置節(jié)點(diǎn)判斷節(jié)點(diǎn)是否相等。
這就有點(diǎn)難辦了，同學(xué)可以先思考如何進(jìn)行解決

假如已經(jīng)進(jìn)入到二叉樹的兩個(gè)子樹判斷，這里就和判斷相同二叉樹一樣了

1.兩個(gè)根節(jié)點(diǎn)都為空返回true
2.只有一個(gè)為空返回false
3.都不為空判斷是否相等

解題代碼：

bool is_Symmetric(struct TreeNode* left,struct TreeNode* right)
{//為空情況if(left == NULL && right == NULL){return true;}if(left == NULL || right == NULL){return false;}//不為空if(left->val != right->val){return false;}return is_Symmetric(left->left,right->right) && is_Symmetric(left->right,right->left);
}bool isSymmetric(struct TreeNode* root) {return is_Symmetric(root->left,root->right);
}

看到代碼想必大家已經(jīng)恍然大悟了
我們可以再創(chuàng)造一個(gè)函數(shù)將root的左右節(jié)點(diǎn)作為實(shí)參進(jìn)行傳遞，這樣就解決只有一個(gè)根節(jié)點(diǎn)指針的問題了

到is_Symmetric函數(shù)中實(shí)現(xiàn)邏輯與上面題相同的樹就一樣了，這里就不再進(jìn)行遞歸圖解了

4、二叉樹的前序遍歷

直達(dá)鏈接：二叉樹的前序遍歷
題目：
解題思路：

對(duì)于前序遍歷在我之前的博客中已經(jīng)講到過，認(rèn)真學(xué)習(xí)了的話對(duì)于前序遍歷大家應(yīng)該是小菜一點(diǎn)的

這題對(duì)第一次做的同學(xué)主要難的有兩點(diǎn)：
1.對(duì)于解題框中preorderTraversal函數(shù)所傳的實(shí)參int returnSize不知道什么意思
2.如何將前序遍歷存入到一個(gè)數(shù)組中*

解題代碼：

//計(jì)算樹的節(jié)點(diǎn)
int Treesize(struct TreeNode* root)
{return root == NULL ?0 :  Treesize(root->left)+Treesize(root->right)+1;
}void preorder(struct TreeNode* root,int*arr,int* i)
{if(root == NULL){return;}arr[(*i)++] = root->val;preorder(root->left,arr,i);preorder(root->right,arr,i);
}//return Size 返回?cái)?shù)組的個(gè)數(shù)
int* preorderTraversal(struct TreeNode* root, int* returnSize) {(*returnSize) = Treesize(root);int* arr = (int*)malloc(sizeof(int)*(*returnSize));int i = 0;preorder(root,arr,&i);return arr;
}

代碼講解：

看了代碼大家就會(huì)知道，returnSize其實(shí)是指所開辟數(shù)組空間數(shù)據(jù)的個(gè)數(shù)，這是力扣中寫題的一貫格式，返回一個(gè)數(shù)組必須計(jì)算出其對(duì)應(yīng)的空間大小。

對(duì)于如何將前序遍歷存儲(chǔ)到數(shù)組中我們看了代碼我想大家就會(huì)明白，而這里需要注意的一點(diǎn)的訪問數(shù)組的下標(biāo)變量i使用的是地址，而不是數(shù)值，因?yàn)樵谡{(diào)用函數(shù)前序遍歷存儲(chǔ)到數(shù)組中存儲(chǔ)一個(gè)數(shù)據(jù)，下標(biāo)i是需要加1往后進(jìn)行移動(dòng)的，而如果傳數(shù)值進(jìn)行下標(biāo)的訪問可能會(huì)出現(xiàn)在同一個(gè)下標(biāo)位置多次存儲(chǔ)的BUG，其原因就是形參只是實(shí)參的一份臨時(shí)拷貝，而要想真正訪問到實(shí)參所對(duì)應(yīng)的數(shù)值就需要傳指針進(jìn)行解引用。

5、另一顆樹的子樹

直達(dá)鏈接：另一顆子樹
題目：
解題思路：

這題看似沒有頭緒，其實(shí)也不難
在判斷是否含有子樹時(shí)，我們可以直接調(diào)用之前寫過的相等的樹的題解（是不是恍然大悟😁）
那么我們需要判斷的只有當(dāng)root的節(jié)點(diǎn)值與subRoot的節(jié)點(diǎn)值相等時(shí)，直接進(jìn)入判斷當(dāng)前子樹與subRoot是否相等即可。
當(dāng)然當(dāng)遞歸到二叉樹的葉子節(jié)點(diǎn)之后為空節(jié)點(diǎn)時(shí)說明root中不含有subRoot子樹

解題代碼：

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//兩個(gè)指針中有一個(gè)為空if(p == NULL && q == NULL){return true;}//其中有一個(gè)為空if(p == NULL || q == NULL){return false;}//兩個(gè)指針都不為空if(p->val != q->val){return false;}return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if(root == NULL){return false;}if(root->val == subRoot->val && isSameTree(root,subRoot)){return true;}return isSubtree(root->left,subRoot)|| isSubtree(root->right,subRoot);
}

我們以下面例子為大家進(jìn)行遞歸圖解：

遞歸圖解：
注意最后判斷對(duì)錯(cuò)用的||
大家可以跟著邏輯捋一遍邏輯（做完圖才發(fā)現(xiàn)不能顯示完整😭，上面遞歸圖解邏輯是從中間開始的大家也可以自己手動(dòng)繪個(gè)圖）

完結(jié)撒?

如果以上內(nèi)容對(duì)你有幫助不妨點(diǎn)贊支持一下，以后還會(huì)分享更多編程知識(shí)，我們一起進(jìn)步。
最后我想講的是，據(jù)說點(diǎn)贊的都能找到漂亮女朋友?