??個(gè)人主頁:?? :???初階牛???
??推薦專欄1: ??????C語言初階
??推薦專欄2: ??????C語言進(jìn)階
??個(gè)人信條: ??知行合一
??本篇簡(jiǎn)介:>:記錄力扣的一些有關(guān)二叉樹的入門題目.分享解題經(jīng)驗(yàn).
c語言實(shí)現(xiàn):單值二叉樹,相同的樹,對(duì)稱二叉樹
金句分享:
?總不能一生碌碌無為,還安慰自己平凡可貴吧.?

前言

二叉樹 主要就是玩遞歸,相信大家學(xué)完 二叉樹 以后,對(duì)遞歸有了更加深層的理解,可以試著做幾道oj題,練一下手.

一、單值二叉樹

聲明:
題目來源于–力扣
題目鏈接: 傳送門

題目描述:

如果 二叉樹 每個(gè)節(jié)點(diǎn)都具有相同的值，那么該 二叉樹 就是 單值二叉樹 。
給定一棵樹,如果這棵樹是 單值二叉樹 時(shí)，
返回 true；
否則返回 false。

示例1:

輸入：[1,1,1,1,1,null,1]
輸出：true

示例2:

輸入：[2,2,2,5,2]
輸出：false

解題思路:

1. 遞歸結(jié)束條件,遇到NULL返回true
2. 判斷根節(jié)點(diǎn)的值與左子樹的值是否相等.
   不相等返回false
3. 判斷根節(jié)點(diǎn)的值與右子樹的值是否相等.
   不相等返回false
4. 返回遞歸遍歷這顆樹的邏輯值.

代碼實(shí)現(xiàn):

bool isUnivalTree(struct TreeNode* root){
    if(root==NULL)
    {
        return true;
    }
    //判斷根節(jié)點(diǎn)的值與左子樹的值是否相等.
    if(root->left&&root->val!=root->left->val)
    {
        return false;
    }
    //判斷根節(jié)點(diǎn)的值與右子樹的值是否相等.
    if(root->right&&root->val!=root->right->val) 
    {
        return false;
    }
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

提交記錄:

二、相同的樹

聲明:
題目來源于–力扣
題目鏈接: 傳送門

題目介紹:

給你兩棵 二叉樹 的根節(jié)點(diǎn) p 和 q ，編寫一個(gè)函數(shù)來檢驗(yàn)這兩棵樹是否相同。

如果兩個(gè)樹在結(jié)構(gòu)上相同，并且節(jié)點(diǎn)具有相同的值，則認(rèn)為它們是相同的。
相同返回:true
不同返回:false

示例1:

輸入：p = [1,2,3], q = [1,2,3]
輸出：true

示例2:

輸入：p = [1,2], q = [1,null,2]
輸出：false

解題思路

1. 先考慮兩棵樹其中一棵為NULl的情況,返回false
   (注意不是指一整顆樹為NULl,而是指一方節(jié)點(diǎn)).
   例如:
   示例2中,第一顆樹的左子樹是值為2的結(jié)點(diǎn),但是第二棵樹的左子樹是NULL.

2. 兩棵樹都為NULL,返回true

3. 判斷兩顆樹的結(jié)點(diǎn)值是否相等.
   不相等則返回false

4. 返回最后遍歷結(jié)果的邏輯值.

代碼實(shí)現(xiàn):

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    //兩方都為空
    if(p==NULL&&q==NULL)
    {
        return true;
    }
    //此時(shí)說明雙方都不為空
    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);
}

提交記錄:

三、對(duì)稱二叉樹

聲明:
題目來源于–力扣
題目鏈接:

題目介紹:

給你一個(gè) 二叉樹 的根節(jié)點(diǎn) root ， 檢查它是否軸對(duì)稱。
對(duì)稱:返回true.
不對(duì)稱:返回false

輸入：root = [1,2,2,3,4,4,3]
輸出：true

輸入：root = [1,2,2,null,3,null,3]
輸出：false

解題思路:

難點(diǎn)在于,對(duì)稱 二叉樹 是需要遍歷到左子樹之后,回到根節(jié)點(diǎn),去與右子樹比較,為了實(shí)現(xiàn)這一要求,我們可以另寫一個(gè)函數(shù),直接將這棵樹用兩個(gè)root訪問.從最開始的根節(jié)點(diǎn)開始,將這顆 二叉樹 切割為 二叉樹 .

1. 創(chuàng)建一個(gè)子函數(shù)check.參數(shù)為(struct TreeNode* root1,struct TreeNode* root2)
2. 先判斷這兩顆樹的根節(jié)點(diǎn)是否為NULL.為空則直接返回true.
3. 一方為NULl時(shí):返回false.
4. 判斷root1的值和root2的值是否相等.
5. root1遞歸時(shí)先訪問其左子樹,root2遞歸時(shí)先訪問其右子樹.
6. root1遞歸 后訪問右子樹,root2遞歸 后訪問左子樹.
7. 返回遞歸結(jié)果的邏輯值.

代碼實(shí)現(xiàn)

bool check(struct TreeNode* root1,struct TreeNode* root2)
{
    if(root1==NULL&&root2==NULL)
       return true;
    //上面已經(jīng)判斷了都為NULL時(shí)的情況,則此時(shí)判斷如果一方為空
    if(root1==NULL||root2==NULL)
        return false;
    if(root1->val!=root2->val)
        return false;
       //注意這里的遞歸順序,重點(diǎn)
    return check(root1->left,root2->right)&& check(root1->right,root2->left);
}
bool isSymmetric(struct TreeNode* root){
   return check(root,root);
}

提交記錄:

練習(xí)完這幾道oj題,相信大家對(duì)二叉樹有了更深層的理解了.
如果文章有幫助的話,可以給牛牛來一個(gè)一鍵三連嗎?
文章來源地址http://www.zghlxwxcb.cn/news/detail-517944.html

到了這里，關(guān)于剛學(xué)完二叉樹,來試試這些oj題練練手吧!的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！