C語言單值二叉樹真題講解
【OJ - 二叉樹】單值二叉樹
LeetCode鏈接：單值二叉樹
題目難度：簡單
一、題目描述
如果二叉樹每個(gè)節(jié)點(diǎn)都具有相同的值，那么該二叉樹就是 單值 二叉樹。
只有給定的樹是單值二叉樹時(shí)，才返回 true；否則返回 false。
二、解題思路
二叉樹的遞歸遍歷，一般都會(huì)把問題拆分成 當(dāng)前樹(根節(jié)點(diǎn)) 和 子樹，然后子樹又進(jìn)行拆分，來解決問題。
核心思路：
1.先判斷當(dāng)前節(jié)點(diǎn)是否為空，如果為空，返回 true（空樹也滿足單值二叉樹的條件）
2.判斷當(dāng)前樹是不是單值二叉樹：
- 先判斷當(dāng)前節(jié)點(diǎn)的左孩子是否為空；
- 將 當(dāng)前節(jié)點(diǎn)的值 與 左孩子的值 進(jìn)行比較，如果相等，在右孩子不為空的情況下，繼續(xù)與 右孩子的值 進(jìn)行比較；
- 如果不相等，說明 當(dāng)前樹 不是單值二叉樹，返回 false。
3.繼續(xù)往下遞歸遍歷，判斷當(dāng)前節(jié)點(diǎn)的左右子樹是不是單值二叉樹。
遞歸過程演示：
如果 a == b && a == c 為真，說明 1 是單值二叉樹。
分而治之，不斷迭代，先判斷 1 是不是單值二叉樹，再判斷 2 是不是單值二叉樹，最后判斷 3 是不是單值二叉樹。
/**
* 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; // 空樹滿足單值二叉樹的條件
}
// 2. 判斷當(dāng)前節(jié)點(diǎn)和其左右孩子是否是單值二叉樹
// 先判斷當(dāng)前節(jié)點(diǎn)的左孩子是否為空，并將當(dāng)前節(jié)點(diǎn)的值與左孩子的值進(jìn)行比較，看是否相等，
// 如果相等，則繼續(xù)往下遍歷；如果不相等，說明不是單值二叉樹，則返回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)的左右子樹是不是單值二叉樹
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語言單值二叉樹真題講解的文章就介紹到這了,更多相關(guān)C語言單值二叉樹內(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
大富翁大家都玩過，走到建筑的位置可以買地，第二圈走到買過的地可以升級(jí)，別人經(jīng)過后需要付過路費(fèi)，每次經(jīng)過起點(diǎn)都會(huì)獲得一定資金，玩到最后還沒破產(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à)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
這篇文章主要介紹了簡單分析C++指針的操作和運(yùn)算的相關(guān)資料,需要的朋友可以參考下2015-07-07
map是一類關(guān)聯(lián)式容器。接下來通過本文給大家分享c++中的map基本操作，需要的朋友參考下2017-05-05
大家好，本篇文章主要講的是C語言的預(yù)處理介紹，感興趣的同學(xué)趕快來看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽2021-12-12
為了消除函數(shù)調(diào)用的時(shí)空開銷，C++ 提供一種提高效率的方法，即在編譯時(shí)將函數(shù)調(diào)用處用函數(shù)體替換，類似于C語言中的宏展開。這種在函數(shù)調(diào)用處直接嵌入函數(shù)體的函數(shù)稱為內(nèi)聯(lián)函數(shù)（Inline Function），又稱內(nèi)嵌函數(shù)或者內(nèi)置函數(shù)2022-05-05
利用C語言模擬實(shí)現(xiàn)qsort,strcpy,strcat,strcmp函數(shù)
這篇文章主要為大家詳細(xì)介紹了如何通過C語言模擬實(shí)現(xiàn)qsort(采用冒泡的方式),strcpy,strcat,strcmp等函數(shù)，文中的示例代碼講解詳細(xì)，感興趣的可以了解一下2022-11-11
這篇文章主要介紹了C++ Boost Graph算法，我門嘗試使用Boost.Graph庫來運(yùn)行Goldberg的最大流算法。 Boost.Graph將其稱為push_relabel_max_flow2022-10-10