【OJ - 二叉樹】單值二叉樹

LeetCode鏈接：單值二叉樹

題目難度：簡單

一、題目描述

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

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

二、解題思路

二叉樹的遞歸遍歷，一般都會把問題拆分成 當(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。