C語(yǔ)言單值二叉樹(shù)真題講解
【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 的條件寫的是，如果左孩子不為空，且當(dāng)前節(jié)點(diǎn)的值 != 左孩子的值，則返回 false，那為什么不寫成：如果左孩子不為空，且當(dāng)前節(jié)點(diǎn)的值 == 左孩子的值，則怎么怎么樣……呢？因?yàn)閷?==，不能直接得出一個(gè)結(jié)果，而寫 !=，就能得出結(jié)果 flase。
到此這篇關(guān)于C語(yǔ)言單值二叉樹(shù)真題講解的文章就介紹到這了,更多相關(guān)C語(yǔ)言單值二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
利用C++和QT實(shí)現(xiàn)Log自定義日志系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了如何利用C++和QT實(shí)現(xiàn)Log自定義日志系統(tǒng),文中的示例代碼講解詳細(xì),具有一定的借鑒價(jià)值,有需要的小伙伴可以參考下2023-12-12
大富翁大家都玩過(guò)，走到建筑的位置可以買地，第二圈走到買過(guò)的地可以升級(jí)，別人經(jīng)過(guò)后需要付過(guò)路費(fèi)，每次經(jīng)過(guò)起點(diǎn)都會(huì)獲得一定資金，玩到最后還沒(méi)破產(chǎn)的就是勝者，本文將制作一個(gè)Matlab版的大富翁小游戲，需要的可以參考一下2022-02-02
詳解Matlab實(shí)現(xiàn)動(dòng)態(tài)表白圖的繪制
這篇文章主要利用Matlab實(shí)現(xiàn)繪制獨(dú)特的表白動(dòng)圖，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)Matlab有一定的幫助，感興趣的小伙伴可以了解一下2022-05-05
C++基礎(chǔ)知識(shí)之運(yùn)算符重載詳解
這篇文章主要為大家詳細(xì)介紹了C++基礎(chǔ)知識(shí)之運(yùn)算符重載，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-02-02
這篇文章主要介紹了簡(jiǎn)單分析C++指針的操作和運(yùn)算的相關(guān)資料,需要的朋友可以參考下2015-07-07
map是一類關(guān)聯(lián)式容器。接下來(lái)通過(guò)本文給大家分享c++中的map基本操作，需要的朋友參考下2017-05-05
大家好，本篇文章主要講的是C語(yǔ)言的預(yù)處理介紹，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽2021-12-12
為了消除函數(shù)調(diào)用的時(shí)空開(kāi)銷，C++ 提供一種提高效率的方法，即在編譯時(shí)將函數(shù)調(diào)用處用函數(shù)體替換，類似于C語(yǔ)言中的宏展開(kāi)。這種在函數(shù)調(diào)用處直接嵌入函數(shù)體的函數(shù)稱為內(nèi)聯(lián)函數(shù)（Inline Function），又稱內(nèi)嵌函數(shù)或者內(nèi)置函數(shù)2022-05-05
利用C語(yǔ)言模擬實(shí)現(xiàn)qsort,strcpy,strcat,strcmp函數(shù)
這篇文章主要為大家詳細(xì)介紹了如何通過(guò)C語(yǔ)言模擬實(shí)現(xiàn)qsort(采用冒泡的方式),strcpy,strcat,strcmp等函數(shù)，文中的示例代碼講解詳細(xì)，感興趣的可以了解一下2022-11-11
這篇文章主要介紹了C++ Boost Graph算法，我門嘗試使用Boost.Graph庫(kù)來(lái)運(yùn)行Goldberg的最大流算法。 Boost.Graph將其稱為push_relabel_max_flow2022-10-10