題目難度：簡(jiǎn)單

一、題目描述

給你兩棵二叉樹(shù)的根節(jié)點(diǎn) p 和 q ，編寫(xiě)一個(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)

• 最大深度： 此樹(shù)為單邊樹(shù)，則深度為 n，最多向下創(chuàng)建 n 個(gè)棧幀，因?yàn)闂瑫?huì)邊用邊銷毀
• 最小深度： 此樹(shù)為完全二叉樹(shù)/滿二叉樹(shù)，則深度為 log2(N+1)