C語(yǔ)言詳解判斷相同樹(shù)案例分析

更新時(shí)間：2022年04月24日 09:10:15 作者：CodeWinter

這篇文章主要介紹了用C語(yǔ)言檢查兩棵樹(shù)是否相同,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

一、題目描述

給你兩棵二叉樹(shù)的根節(jié)點(diǎn) p 和 q ，編寫一個(gè)函數(shù)來(lái)檢驗(yàn)這兩棵樹(shù)是否相同。

如果兩個(gè)樹(shù)在結(jié)構(gòu)上相同，并且節(jié)點(diǎn)具有相同的值，則認(rèn)為它們是相同的。

LeetCode鏈接：相同的樹(shù)

二、解題思路

核心思路：

先比較兩顆二叉樹(shù)的根節(jié)點(diǎn)

如果「都為空」，則返回 true，說(shuō)明兩樹(shù)相同。
如果「一個(gè)為空一個(gè)不為空」，說(shuō)明這兩顆樹(shù)不相同，則返回 false。
如果「都不為空，但節(jié)點(diǎn)值不相同」，說(shuō)明這兩顆樹(shù)不相同，則返回 false。
經(jīng)過(guò) 1 和 2 和 3 的判斷，說(shuō)明根節(jié)點(diǎn)「都不為空，但節(jié)點(diǎn)值相同」，則當(dāng)前節(jié)點(diǎn)相同。我們繼續(xù)遞歸遍歷，比較它的左子樹(shù)和右子樹(shù)的根節(jié)點(diǎn)。

遞歸過(guò)程演示：

依次比較兩顆二叉樹(shù)中「當(dāng)前樹(shù)(1、2、3、4、5、6)的根節(jié)點(diǎn)」是否相等，這樣每個(gè)節(jié)點(diǎn)都被比較了一次。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    // 1. 先比較兩顆樹(shù)的根節(jié)點(diǎn)
    // 都為空，返回true，說(shuō)明滿足相同的樹(shù)的條件
    if(p == NULL && q == NULL)
    {
        return true;
    }
    // 一個(gè)為空一個(gè)不為空，返回false
    if(p == NULL || q == NULL)
    {
        return false;
    }
    // 都不為空，但節(jié)點(diǎn)值不相等，返回false
    if(p->val != q->val)
    {
        return false;
    }
    // 2. 經(jīng)過(guò)前面的if的判斷，既然運(yùn)行到這里了，說(shuō)明當(dāng)前節(jié)點(diǎn)相等
    // 則繼續(xù)比較左子樹(shù)和右子樹(shù)的根節(jié)點(diǎn)
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

時(shí)間復(fù)雜度：假設(shè)兩棵樹(shù)都有 n 個(gè)節(jié)點(diǎn)，最多比較 n 次，所以為 O ( N ) O(N) O(N)

空間復(fù)雜度：往下遞歸會(huì)開(kāi)辟棧幀空間，函數(shù)返回時(shí)會(huì)還給操作系統(tǒng)，所以「空間復(fù)雜度」和「遞歸的最大深度」有關(guān)，最壞情況下，「遞歸的最大深度」就是有 n 的節(jié)點(diǎn)二叉樹(shù)的最大深度，所以為 O ( N ) O(N) O(N)