C語言單值二叉樹真題講解

更新時間：2022年04月24日 09:53:22 作者：CodeWinter

單值二叉樹你可能之前沒見過，如果二叉樹每個節(jié)點都具有相同的值，那么該二叉樹就是單值二叉樹，讓我們通過一個真題來深刻了解它吧

一、題目描述

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

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

二、解題思路

二叉樹的遞歸遍歷，一般都會把問題拆分成當前樹(根節(jié)點) 和子樹，然后子樹又進行拆分，來解決問題。

核心思路：

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

2.判斷當前樹是不是單值二叉樹：

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

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

遞歸過程演示：

如果 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. 先判斷當前節(jié)點是否為空
    if(root == NULL)
    {
        return true; // 空樹滿足單值二叉樹的條件
    }
    // 2. 判斷當前節(jié)點和其左右孩子是否是單值二叉樹
    // 先判斷當前節(jié)點的左孩子是否為空，并將當前節(jié)點的值與左孩子的值進行比較，看是否相等，
    // 如果相等，則繼續(xù)往下遍歷；如果不相等，說明不是單值二叉樹，則返回false。
    if(root->left && root->val != root->left->val)
    {
        return false;
    }
    if(root->right && root->val != root->right->val)
    {
        return false;
    }
    // 3. 往下遍歷，判斷當前節(jié)點的左右子樹是不是單值二叉樹
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

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

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

您可能感興趣的文章: