【OJ - 二叉樹(shù)】單值二叉樹(shù)

LeetCode鏈接：單值二叉樹(shù)

題目難度：簡(jiǎn)單

一、題目描述

如果二叉樹(shù)每個(gè)節(jié)點(diǎn)都具有相同的值，那么該二叉樹(shù)就是 單值 二叉樹(shù)。

只有給定的樹(shù)是單值二叉樹(shù)時(shí)，才返回 true；否則返回 false。

二、解題思路

二叉樹(shù)的遞歸遍歷，一般都會(huì)把問(wèn)題拆分成 當(dāng)前樹(shù)(根節(jié)點(diǎn)) 和 子樹(shù)，然后子樹(shù)又進(jìn)行拆分，來(lái)解決問(wèn)題。

核心思路：

1.先判斷當(dāng)前節(jié)點(diǎn)是否為空，如果為空，返回 true（空樹(shù)也滿足單值二叉樹(shù)的條件）

2.判斷當(dāng)前樹(shù)是不是單值二叉樹(shù)：

• 先判斷當(dāng)前節(jié)點(diǎn)的左孩子是否為空；
• 將 當(dāng)前節(jié)點(diǎn)的值 與 左孩子的值 進(jìn)行比較，如果相等，在右孩子不為空的情況下，繼續(xù)與 右孩子的值 進(jìn)行比較；
• 如果不相等，說(shuō)明 當(dāng)前樹(shù) 不是單值二叉樹(shù)，返回 false。

3.繼續(xù)往下遞歸遍歷，判斷當(dāng)前節(jié)點(diǎn)的左右子樹(shù)是不是單值二叉樹(shù)。

遞歸過(guò)程演示：

如果 a == b && a == c 為真，說(shuō)明 1 是單值二叉樹(shù)。

分而治之，不斷迭代，先判斷 1 是不是單值二叉樹(shù)，再判斷 2 是不是單值二叉樹(shù)，最后判斷 3 是不是單值二叉樹(shù)。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isUnivalTree(struct TreeNode* root){
    // 1. 先判斷當(dāng)前節(jié)點(diǎn)是否為空
    if(root == NULL)
    {
        return true; // 空樹(shù)滿足單值二叉樹(shù)的條件
    }
    // 2. 判斷當(dāng)前節(jié)點(diǎn)和其左右孩子是否是單值二叉樹(shù)
    // 先判斷當(dāng)前節(jié)點(diǎn)的左孩子是否為空，并將當(dāng)前節(jié)點(diǎn)的值與左孩子的值進(jìn)行比較，看是否相等，
    // 如果相等，則繼續(xù)往下遍歷；如果不相等，說(shuō)明不是單值二叉樹(shù)，則返回false。
    if(root->left && root->val != root->left->val)
    {
        return false;
    }
    if(root->right && root->val != root->right->val)
    {
        return false;
    }
    // 3. 往下遍歷，判斷當(dāng)前節(jié)點(diǎn)的左右子樹(shù)是不是單值二叉樹(shù)
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

代碼中有個(gè)小思路，我們 if 的條件寫(xiě)的是，如果左孩子不為空，且當(dāng)前節(jié)點(diǎn)的值 != 左孩子的值，則返回 false，那為什么不寫(xiě)成：如果左孩子不為空，且當(dāng)前節(jié)點(diǎn)的值 == 左孩子的值，則怎么怎么樣……呢？因?yàn)閷?xiě) ==，不能直接得出一個(gè)結(jié)果，而寫(xiě) !=，就能得出結(jié)果 flase。

到此這篇關(guān)于C語(yǔ)言單值二叉樹(shù)真題講解的文章就介紹到這了,更多相關(guān)C語(yǔ)言單值二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論