??目錄

一，單值二叉樹

題目詳情：

解法：父子比較法

解題思路：

思路實現(xiàn)：

源代碼：

二，相同的樹

題目詳情：

解法：比較法

解題思路：

思路實現(xiàn)：

源代碼：

三，翻轉(zhuǎn)二叉樹

解法：替換法

解題思路：

思路實現(xiàn)：

源代碼：

一，單值二叉樹

題目詳情：

如果二叉樹每個節(jié)點都具有相同的值，那么該二叉樹就是單值二叉樹；

只有給定的樹是單值二叉樹時返回?true；否則返回?false；

提示：

1，給定樹的結(jié)點樹范圍是【1，100】

2，每個結(jié)點的值都是整數(shù)，范圍為【0，99】

示例1：

輸入：nums = [1，1，1，1，1，NULL，1?]

輸出：true

示例2：

輸入：nums = [2，2，2，5，2]

輸出：false

解法：父子比較法

解題思路：

以上圖為例：要判斷根結(jié)點為（2）的二叉樹是否為單值二叉樹可以分解為（2）的左右子樹是否為單值二叉樹，這就很符合遞歸思路可以用遞歸解決；【（2）= 左子樹 && 右子樹】

判斷條件：

當(dāng)結(jié)點為NULL時返回 true ；

當(dāng)子結(jié)點存在時，并且與父親結(jié)點的值不相同時返回 false；

思路實現(xiàn)：

首先要判空：

//判斷空
if(root==NULL)
{
    return true;
}

?當(dāng)結(jié)點為空時不影響父親孩子之間的關(guān)系；

然后判斷孩子，父親之間的值的關(guān)系：

//判斷孩子與父親的值
if(root->left && root->val!=root->left->val)
{
    return false;
}
if(root->right && root->val!=root->right->val)
{
    return false;
}

?判斷孩子，父親所對應(yīng)的值是否相同；

大事化小：以上條件都滿足時，還需左右子樹是否為單值二叉樹，只有當(dāng)左右子樹都為單值二叉樹時才為 true；

//化為兩顆子樹是否為單值樹
return isUnivalTree(root->left) && isUnivalTree(root->right);

?要用邏輯與，需要雙方為真時才返回 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);
}

我們可以用示例來演算一遍，流程也是這樣的；

像這種遞歸題目要演算其過程需要畫圖，這樣才是最直觀的；

二，相同的樹

題目詳情：

給你兩棵二叉樹的根結(jié)點?p 和 q?，編寫一個函數(shù)來檢驗這兩棵樹是否相同；

如果兩個樹在結(jié)構(gòu)上相同，并且結(jié)點具有相同的值，則認(rèn)為它們是相同的；

提示：

兩棵樹上的結(jié)點數(shù)目都在范圍【0，100】內(nèi)

-104<=Node.val<=10?

示例1：

輸入：p = [ 1，2，3 ]，q = [ 1，2，3 ]

輸出：true

示例2：

輸入：p = [ 1，2 ]，q = [ 1，2?]

輸出：false

示例3：

輸入：p = [ 1，2，1?]，q = [ 1，2，2 ]

輸出：false

解法：比較法

解題思路：

要判斷兩棵樹是否一致，要考慮的是他們的結(jié)點是否都存在，結(jié)點對應(yīng)的值是否相同；

以上圖為例：根結(jié)點相同了，還要判斷其左右子樹是否也相同，然后層層往下，這道題也是用遞歸思想；

思路實現(xiàn)：

首先要判斷他們的結(jié)點是否對應(yīng)存在：

    //雙方都為空
    if(p==NULL && q==NULL)
    {
      return true;
    }
    //一方為空另一方不為空
    if((p==NULL || q==NULL) 
    {
      return false;
    }

當(dāng)雙方對應(yīng)的結(jié)點都為空時返回 true；

當(dāng)雙方對應(yīng)的結(jié)點只有一方為空，另一方不為空時，返回 false；

然后判斷它們對應(yīng)的結(jié)點的值的情況：

    //判斷所對應(yīng)的值是否相同
    if(p->val != q->val)
    {
      return false;
    }

當(dāng)所對應(yīng)的值不相等則返回 false；

大事化?。?/strong>當(dāng)以上條件都滿足時，還需要判斷這兩棵樹所對應(yīng)的左右子樹是否相同；

    //判斷其對應(yīng)的左右子樹是否也相同
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    //雙方都為空
    if(p==NULL && q==NULL)
    {
      return true;
    }
    //一方為空另一方不為空
    if((p==NULL || q==NULL) 
    {
      return false;
    }
    //判斷所對應(yīng)的值是否相同
    if(p->val != q->val)
    {
      return false;
    }
    //判斷其對應(yīng)的左右子樹是否也相同
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

void swap(struct TreeNode** left,struct TreeNode** right)
{
    struct TreeNode* tmp=*left;
    *left=*right;
    *right=tmp;
}

struct TreeNode* invertTree(struct TreeNode* root){
    //判空
    if(root==NULL)
    {
        return NULL;
    }
    //交換
    swap(&root->left,&root->right);
    //左子樹翻轉(zhuǎn)
    invertTree(root->left);
    //右子樹翻轉(zhuǎn)
    invertTree(root->right);
    return root;
}